Since there is no good way to do an on-line upgrade from CentOS/RHEL 3 to CentOS/RHEL 5, that isn't really an option at this time (too much downtime).
..
This is one huge reason why I like gentoo so much.
It has nothing to do with gentoo, IMHO.
It has in that way, that there are no releases, no big jumps with lots of breakage and config file syntax changes... But I definitely wouldn't say Gentoo is a good distribution for systems that need to be highly available. (I'm using Gentoo myself on desktops and servers, but none of them do run really critical stuff).
I agree - I use gentoo on all my main servers after having painted myself into a corner like you with Redhat 7.1 some years back.
The machine which replaced that Redhat 7.1 machine (you do the maths) is running nicely here still and hasn't had an "upgrade" since - it just gets updated with key packages from time to time
My next major epiphany has been virtualisation. The machine mentioned above if end of life now (1Ghz machine) and the replacement which is coming online uses vservers with near every major service in it's own vserver instance. This is just fantastic
If you switch to virtualisation on your next upgrade you will find youself in this same situation, but this time you can boot up a copy of the main machine - upgrade it, then within seconds kill the old machine and start the new machine up as the live master (I keep the data separate to the virtual machine instance so I can boot up two instances both playing with the same data)
It's fantastic for web hosting also - got a new app which you don't trust - couple of mins later you can spin up a new server and stick it all on that!
Vservers are nice low weight virtualisation and work well for me. I started with a smallish stage4 hardened gentoo tar file (ie roughly you zip up a working server) and then I customised that in several major ways, eg one with apache, another with nginx, another clean. Then I can use any of those base installations as a starting point for a new server. I keep all the vservers as similar as possible for ease of installation and basically I test upgrading one, then the others use the compiled packages and update in around 10 mins for the whole machine.
It's very cool also to get a machine into a state where you think a reboot is the quickest fix and realise that this takes about 3-4 seconds only with a quickly "vserver mail1 restart" !! Wahey!
Ed W