Recompiling MySQL doesn't sound like a big deal to me, and there has to be a way to sneak around the "-" limitation (convert it to a letter sequence?), but you may have found the sweet spot for satisfying this requirement. If it's fast enough then you're done, and you know you can always do one of these things later.

Inverted index searches do scale very well, since they are basically just one hash lookup per keyword being searched. I've sometimes taken advantage of this speed by encoding fields like mfg and material as special keywords. It scales well for a large data set.