Soldato
Fees always stay the same, there are cheaper places but vida's service is the best out there.
The service is bloody great. I have a VM with them that costs around £25 a month and every time I've needed help with something, they've responded with someone that has a clue in 10 minutes and resolved it in 30-120 minutes. That includes doing custom OS installs.