here are two places one is the company i work for and im prety sure you can get route access and the other it ses they can give you route access.
Think? hosting | Dedicated Hosting
Dedicated server hosting from 123-reg
i can try and find more if you need these are just one's i now off also
you might wan't to ask henigs where this website is i now he runs on dedicated but i don't now if they give you root access i hope this helps you.
personaly i think you have made the right choice about not trying to host it your self.
__________________
Look what my computer did to me:

shouldn't it be the other way around..
---------------------------------------------------
Here to help others with computer problems and learn new things at the same time. No one knows everything, if they did, life would be pointless.
not bad for a 512KB conection which is the fastest i can get!!!!!