vB 3.5 I presume? Don't use the FULLTEXT search option for one thing. Use the vB search (ACP > vB options > Search Type).
Also, from the ACP > vB Options > vB Options:
Message Searching Options > Search Index Minimum Word Length - lower to what you need. Lower values mean slower searches and a larger search index.
Message Searching Options > Words to be excluded from search - adjust as necessary.
Message Searching Options (Default Search) - go through the options on that page, inparticular Words to be Included Despite Character Limit
Message Searching Relevance Options (Default Search) - no need to fiddle with much here, but you may want to tweak. I haven't tweaked mine.
All I can say is thoroughly go through the vB options. It took me about an hour, and then another hour or so to setup all the forum permissions, but it's worth it. Oh, and don't give the Unregistered users group the ability to edit their posts, because vB thinks Unregistered = anyone...so anyone can edit guests' posts...I didn't do that, honest...
