I can recommend http://www.ServerXtreme.com/
* They provide what they promised
* Their network connectivity is tops (I get players from all over the world with very low pings)
* They do not overburdon their boxes so CPU load is not a problem
* The servers are "watchdoged" so if the process crashes, it gets restarted a minute later.
* They offer Redirect capacity
* I have pretty much complete control over configuration
I should say though that if you're planning a heavy UT2K4 box, you should ask them if they can set you up with a 64BIT AMD system, possibly an Opteron. These boxes seem to be the only trouble free way to run ONS with 32 players.
You should also know that they are a Unix house.
Good luck, and let us know what you decide.