Если mail.ru то ещё можно парсить с "моего мира" пол, и то не факт, что юзер там есть. короче говоря, к каждому "мылодателю" свой подход нужен.
Если все мыла одного почтового сервера(напр. mail.ru)то авторизовываемся, заходим сюда http://e.mail.ru/cgi-bin/userinfo?mra=1 и парсим указанный пол. Только с таким количеством это займет много времени
Отсортировать можно, но далеко не с 100% точностью. В некоторых мылах, например, очевидно транслитерованное имя будет ну или что-то подобное.
