I saw someone else post about Vserver.com
I have to agree they are pretty good.
They offer good support, maintenance and regular upgrades on all their servers.
And to answer your question about php4.0
Yes, they just upgraded to it within the last few weeks.
As far as the pricing goes, it's better than what the other person stated, I have a 250meg virtual server for 95.00 a month
They do offer dedicated hosting, and a number of choices for platform, OS and HardWare configurations.
Being the happy camper that I am with them, I plan on sticking with them for a while.
As far as who NOT to host with....
I have to say Verio is your worst bet, they suck hard, I had a client that was paying 160.00 for 150megs with perl5.02 (this was 3mos ago!) and no way to upgrade (since the x11 lib's were only accessible as root) And of course, their solution was, "spend more for a newer virtual server (their new freeBSD servers) upgrade or rot"... in not so many words, but it's basicly what they said : ]