if it helps at all, I am UK based and use www.swishhosting.co.uk
Its £2.67 a month but you can have multiple dbases and it includes email and great support.
Both Linux an Windows are available
I have multiple PCMS and Gallery installations on their servers and all work very well....