[Zebestov]

Хранить в базе два ника:

1. отображаемый
2. для проверки

Первый ник хранится в оригинальном виде, как его ввел пользователь.
Второй ник получается из оригинального следующим путем:

1. заменяем следующие знаки на русские аналоги: A, B, C, E, H, K, M, O, P, T, X, a, c, e, m, o, p, u, y, 6
2. переводим все в нижний регистр

С каждый новым вариантом ника производим эту же процедуру и проверяем на существование такого же в базе (по второму нику).

Добавлено через 11 минут
А если добавить еще букву "g", то не пройдут и такие варианты:

Mopgop
O6og
Cugop
и т.д.

(все написано латинскими буквами)