Well - you're going to be running into some serious compromises. For one - "30 100-character fields" sounds like someone's being sloppy/lazy with giving you the right specifications. You really ought to push a little harder to get them to give you some ACTUAL specifications (there are thirty possible, optional pieces of data - let's define what they are, and let's type them appropriately to what they REALLY are). You will likely find out that several of those will be very precise fields, which can be typed correctly, indexed correctly, etc...

You should also push to verify that they will use EVERY metadata element in their optional searching

In the meantime, Grant's solution should still provide you with some amount of gain. That being said - you NEED the full-text index on the 100-varchar field, since traditional indexes are worthless/not used in a lot of LIKE syntaxes. Anything other than a Like 'abcdef%' syntax will require a table scan.