From what you describe .. for some reason your initial Apple registration file was missing or corrupt.. That file is typically located in
/private/var/db/.AppleSetupDone
Hard to tell how it really happened....but I'd say you are on the right track using cloning software to get out of these situations. Super Duper is another option.
If have or can acquire an external USB or Firewire drive for the tower, you could make it bootable and have a known good disc image of the G5 on it to restore from...