Your advertising strategy shouldnt be like "Spend $100 for this month & stay away for next 3 months and spend again".

It is not an advertising strategy at all. Determine a lowest possible amount you can afford every month, Even you have no sales for that particular month!

Your advertising budget should be like your monthly electricity/telephone bill.

I hope at least a minimum of $50 to $75 is good to start with.

Grab a stable place in a 5-4 digit alexa ranked website for your banner.

http://buysellads.com/buy is a great place for finding publishers within your budget range.

No one can guarantee that you will get orders worth of $500 from your first $50. You may get an order or a lead or just visitors.

But keep spending same amount for following months. If You feel that particular website is not bringing loyal visitors then, Try an another website within your same budget.

If you have $300 to spend for advertising, Then dont give it to a single website.

Buy 3 different website locations worth of $50 and let your ad be there for 2 months. Thats a lot better than buying a premium spot in a single website.

Sometimes I get awesome offers, When I tried to communicate directly with bloggers and webmasters(who doesnt know buysellads exists)

I would say none of the above. The best way is local marketing, that is approaching local businesses in your area.

The second one is probably through forums like WHT and dozens of other forums for webmasters.

You can get a decent return using banner ads on the Google Adwords network.

1) Get an effective banner(s) designed
2) Upload banner into Google Adwords
3) Select your campaign to run on CPM (cost per impression) instead of CPC
4) Let the sales start coming in.

This is a low cost way to drive sales in. CPC with text links work well too, but is very expensive for Web Hosting related keywords.

The advertising strategy completely depends on where your audiences inhabit.
1. Google Adwords - Very wide range of audiences
2. Hosting Directory PPC Program - Occasionally Spotted, Directories charge more and the budget might be huge for Startup companies. ROI might be very less
3. Banner Ads - Works well if your company comeup with insane deals/products on Hosting or If you are Giant Host with crazy deals.
4. Email Marketing - Very wide range of clients. After finalizing your niche you can contact webmasters running specific forums to email with some deals.

You have missed

5. Local Magazine Ad
6. Radio Ad & TV Ad
7. Print Disribution
9. Social Marketing

Thanks, thats very helpfull

From a small business perspective, PPC or PPA advertising is effective since it is a very good way to quantitatively see what you're getting for your money.

That said, you can also burn through a lot of capital very quickly if you don't know what you're doing.

Don't forget about the free advertising available out there.

i.e. WHT :)

Which PPC Program can be recommended ?

Very nice advice from blazenetworks and banaz - thank you.

none of the above..

try more traditional methods. Direct, physical mailings. Radio segments, TV segments, etc.. dollar for dollar, traditional marketing strategies beat out online strategies all day long. More cost effective, better results, etc.. online marketing just leads to having a better banner and cheaper price then the banner next to you. Same with google adwords, etc.. piss poor marketing strategies and exactly why so many hosting companies fail..

Nice feedback BN. & Yes I would recommend a nice budget for paid marketing.

1. Ad on forums hardly work
2. I dont like to work with google as it only siphons out money with less results
3. The only hard hitting technique would be advertise locally and hire some experts to make cold calls using a yellow pages (sure that would pay off)

I have tried Adwords, but I am quite disappointed.

It might have been me not targeting the right people.... but I have had much better results with word of mouth from existing customers.