Dovresti usare le espressioni regolari: o mettere come clausole nelle ricerche (ci sono in mysql le regexp ?) oppure una volta trovate le righe contententi la parola parsarle una ad una es escludere quella che non vanno bene.
Il secondo a me sembra una cosa abbastanza più lenta, ovviamente se limiti la query ai primi 20 risultati e poi dividi in pagine il carico diminuisce