Yeah you might be right, it sure seems like it's been that long. I'm sure it was here in 06, 9 months is plenty of time to put in "select * where title like '%query%';"
Doing search right is not just a matter of searching titles. And unless you're prepared to work hard to get it right, you're probably not going to do better than Google.
Adding a sitemap might help Google index the old pages better. Adding date-based archive links (like many blogs do) would probably help as well (making the site structure more like a tree and less like a list).
