Yeah, it sounds like you need to expand out to a VPS. There are tons and tons of VPS plans out there for under £30 (£30 would likely be more of a mid-range VPS in most cases). What I think is an important decision is if you want to host in the US or the UK. I am not sure what the VPS option is if you want to host on a UK IP, but I can only assume there are tons, probably at comparable prices to the US market since the hosting market is global and everyone is in competition.
I have not had a VPS myself, but I know several people here have used
Dreamhost and seemed to like it, and this website is hosted by
A Small Orange, which I believe Halls likes pretty well (and you can see the site runs pretty well, too; better than it has on its previous host, that is for sure). Maybe he will chime in with his experience so far with them.