If you were listed on FFA and other type sites, those have a very short shelf life, as well as potentially damaging to your site.
Also, keep in mind you'll get different results also depending on how your search.
link:domain.com
link:
http://domain.com
link:
www.domain.com
link:
http://www.domain.com
can all potentiall bring up different results.
It could also be that your linking schemes that are very obvious on your "links" pages from the bottom of your index page are now backfiring.
Yahoo and MSN are both also taking great pains to take more legitimate strides in cleaning up their search results - if none of the above applies, it could be that you've done nothing wrong, just that the engines have applied new results, standards, etc.
Out of curiosity, your website says it hosts over 167000 websites, but you've only been online for since March 2005 ... sounds a bit "optimistic"?