Get a different host for sure, there is no reason that a hosting company shouldn't be allowing PHP unless they don't want to mess with the security and that's not good for the web builders at all. You will need PHP at some point for so many things that it's pretty much a necessity for building websites these days. The host you have is just plain stupid and they need to get realistic or go out of business lol.

Well it's Virgin Media and I phoned them up and the answer I got was seemingly they don't allow PHP....

Virgin Media is an ISP, not a hosting company.

If you are talking about the free webspace that you get with Virgin Media, then they do not allow the running of any scripts.

They have their own cgi script that can be used for putting a contact form onto a page, but it is only basic.