#Ищем пользователей с именем, написанным только латинскими буквами
SELECT * FROM users WHERE name ~ '[a-z]+';
#ищем с русскими буквами
SELECT * FROM users WHERE name ~ '[а-я]+';
А вы не смотрели в сторону Sphinx или, например Zend Lucene. Это первое, что пришло в голову. Хотя, честно говоря, не уверен, насколько они подходят для конкретной задачи.