Hello Murdock,
WebColos is working with MySQL 5 and PHP 5.2 and you can work with PLESK. There cheapest package is £ 9.99 a/year incl VAT with 300 MB Disk and 10 GB traffic. You pay afterwards.
Of course there are more packages when this is not enough. Look at there site
www.webcolos.co.uk .
I hope I gave you enough information.
Pepijn