думаю, что в базу точно заносится доп. ящик, указанный при регистрации
а так же фиксируются все смены паролей, рег.данных, попытки восстановить пароль и время заходов (хотя бы время последнего захода).
Если так и есть, то зная эту инфу, восстанавливать можно хоть до посинения...

А то, что ящики иногда не восстанавливаются владельцами, то это проблема хозяев, которые по своей неграмотности либо не знают, как вернуть ящик, либо им не пользуются, либо забивают и заводят новый.