I have my company's site on the web for my small company. When new
clients search by search engine (Yahoo/Google/MSN...), they see only
few links that mention my company/website name... That looks bad when
a new client wants to know about how big we are... The search kind of
tells them that we are too small and no one talks about us...

I am not looking for something that mentions us and in a week or a
month take us off... I want something to mention and keep us... so I
hope to see the same release two years from now

I want to post a press release or something, see my site/company name
on many sites... My goal is when my new client search on
Google/MSN/Yahoo.... they see people talking about us (I hope to get
the big news paper name to mention us). I also want that press release
(for example) to stay (not to be deleted after a month or two)... I
don't mind to pay around $100-200.00 (or more if I really have to) if
my web site name/company will be having a permanent release on the big
news site...

I wish I can show on the main page of my site couple of big news
papers that talk about us.

Please advice

The best way I have found to move up on the search engines is to get a
link in a mainstream press article. Enter competitions,you need to
actually do things, in other words you need to deserve to get a better
ranking. Become a speaker at a conference, they will have a link back
to your company as part of your speakers bio.

How about charity events, these get press, and press gets links and
links gets higher movement up on hte search engines.

Basically get out and about and out of your "small office"