I'm afraid I can't offer any help but I have exactly the same problem on probably the same machine (2x2.5 GHz Powermac G5 (June 2004)). It first started a few months ago and one time it took about 48 hours before it would restart. I was about to take it in to be looked at and just gave it one more try and it started. I leave it on all the time now, it restarts okay when required after software updates etc but if it has to be shut down it just acts dead until it decides to come round in its own time. It's hardly eco-friendly but I have to leave it running continuously because I can't put it to sleep. I have a UAD audio DSP card in it and that prevents sleep without disabling drivers for the card which I've found to be a bit flakey in the past so I want to avoid that too.
When the machine is up and running it runs along very smoothly under fairly heavy audio workload. Until today it has been a couple of months since I've had to shut it down fully. I installed the new Logic Studio update and had a kernel panic on AUval when I launched Logic 8 for the first time.
I found this thread when I decided to look and see if anyone else was suffering the same start up problem and had hopefully found a solution. This specific start up problem seems pretty rare. It has crossed my mind that since we both seem to do audio work that perhaps there's something common on our systems that has caused this but that's a long shot. I couldn't pinpoint any hardware or software change I'd made at the time it first occured, just came out of the blue.
I've tried everything at various times, resetting PMU, removed and reseated all RAM, tried to start with most of RAM out, reseated the video card, removed the PCI cards, changed the battery, zapped PR, reset open firmware, ran Apple Disk Utility and Disk Warrior on drives, ran Apple hardware tests and Tech Tool Pro tests etc etc. I even checked the voltage coming out of the power supply one time and that was apparently okay too even though the machine was in a dead phase. Nothing seems to make any difference and it just comes round in its own time.
Today it's been dead for approx 4 hours and counting. I don't need to use it over the weekend so I'll see if I can get it to start up again before Monday.
I get the feeling that something is gradually failing and it'll have to be serviced eventually but I'm trying to persevere with this until something falls over completely and it won't start at all. I'll keep you posted on any progress I make.