If you know how to manage a server by yourself, there are a lot cheap solutions outside.
If you don't know how to manage a server, take a company which offers a per hour rate for server management. I have seen some good and cheap offers from established companies like
m3servers or
swiftco . Don't go with one man companies.
If you are satisfied with your hosting company, ask them for a deal. I am sure they don't want to lose a paying customer.