mysql accent insensitive and dotted insensitive search

Just use an appropriate collation. For instance:

create table test(
    foo text
) collate = utf8_unicode_ci;
insert into test values('Agüeda');
insert into test values('Agueda');
select * from test where foo = 'Agueda';

This gives your two rows.

1) Write your own collation. latin1_general_diacriticinsensitive. I wouldn't even know where to begin, though :).

2) Use regex and character groups: /[uü]ber/

3) The Solution In Your Mind. I'd personally use this, since design is all about compromise and this is a simple solution with just a 100% space overhead. Granted, the space overhead might eventually turn into a speed overhead, especially with MySQL, but that's to worry about later. This is also very easy to undo if need be.