REGEXP and accented vowels

Hi:

I would like to know if queries to a MySQL database using REGEXP are being done on the index file in order to do a fast search.

I need to use REGPEXP in order to search for items in a database with accented vowels:

SELECT * FROM table WHERE title REGEXP "m[eé]xico"

the database may have words like 'mexico' and méxico'.

Our queries are taking more than 4 seconds.

Also, is there any other way to query a database for accented/non accented characters, perhaps using LIKE?

Thanks,

Mark