Don'tgive up on PPC, don't take this the wrong way but maybe your not doing it the right way?
Also have you tried affiliate links? If you set up as a affiliate I would be happy to add a link to my hosting review site. Then people can rate your services and those looking for a reliable company will choose you if your good.
Another way to get clients is to buy up other hosting companies, you can pick them up for reasonable prices.
It takes time to build the sort of business your building but the rewards can be massive.
I think you could do is write articles, provide offers in the forums, blog about it and social networking sites. I think this way you can get good traffic as well.
You could try to advertise in some smaller forums..they wont charge as much as the big ones. I'm not sure what webmaster-talk charges, but since its a large forum, I can't see it being cheap since your ads would be exposed to 100,000+ members not counting unregistered visitors. You can also try advertising on http://webhostingtalk.com which is specifically a "hosting" forum, which is very large as well. You have more than enough posts to post in the marketplace. Also, what makes this company stand out from the others? If you can offer something better/different than everyone else..there ya go. Advertise discounts and promo codes or allow people to sign up for an affiliate program....
You advertise that your company has an affiliate program. Each person that signs up as an affiliate get a percentage of each sale they bring to the table...thus making them money as well. If they want to make more money, they'll try to get you more business...
Also, I see on your site that you utilize Vmware. Virtualizing servers is considered a "green" initiative...you could use this as a marketing strategy too...fyi...
I meant, you said you can post a topic in a forum if it's a right forum about the service taht your website is offering. But your website requires registration, and if you provide the link, it seems a bit advertising... how do you do that?
Website requires registration for what? I don't want to hi-jack this thread from the original post, so you may want to start your own thread to get some more input.