username+randomstring@g[oogle]mail.com should be normalized to username@gmail.com, as well. I used a custom extension for MtGox that wasn't found.
That said, really useful service. On the other hand it's sad that we actually need something like this.
The other way around, too. If I put in "pavel.lishin@gmail.com", it would be nice if it informed me that "pavel.lishin+iharvestbitcoinsalldumbday@gmail.com" was compromised.
And any variation with periods in the username: spoold@gmail.com == s.pool.d@gmail.com == spo.old@googlemail.com
Technically, username+randomstring@* should be normalized to username@* ; plus in email address is part of the standard.
Or instead of checking by email domains of individual accounts, add an option to search by the domain of the site you are concerned about.