1) Для всех распространенных сервисов вроде мру, яши, гмейла и прочих, через веб-морду можно проверить существование ретривом или регой. У многих на это даже специальный скрипт для аякса есть.

2) Как правило, серверы отвечают о несуществующем аккаунте, если на него попробовать отправить письмо.

3) Попытка авторизации под несуществующим логином для некоторых может сработать, а некоторые серверы одинаково отвечают как на существующий, так и на несуществующий логин. Недавно наткнулся на подобную багу в vsftpd. very secure.

4) Посмотрите в сторону софтин smtp-user-enum и swaks. Первая предназначена делать ровно то, что вам нужно, вторая является чем-то вроде netcat для smtp.