My 2c:
1. Kosta, if you want to build an advanced search (or maybe just improve the current search) check out
MySql's Full Text Search Functionality.
2. On the keyword front (or rather themes as underdogs calls them) I think it would be brilliant to standardise on these. What I mean by that is actually have the same themes and make sure all games fall into the same themes as underdogs (and any other abandonware site that wants to participate). It would be much better if games on all the abandonware sites get sorted into the same categories, less confusions and easier to search for. Plus it helps as underdogs already have their games sorted and we could use that data to update our games (at least the ones that are the same).
3. I think it would be best to leave the search box at the top as is (as a quick search) and then have a separate page available from the left-hand menu which would have the advanced search facilities. This is how it's mostly done over the net and I don't see any reason to deviate from the norm (think google).
(Heh, I can just see the developer in me talking from points 2 & 3
)