Про POP3 -- в принципе, могу предположить, в чем дело... в порядке сообщений на свервере. POP3 это никак не задает, и сообщение в папке может оказаться "позади" непрочтенных.
А так как состояния сообщений (прочтено / непрочтено) в POP3 тоже нет... В общем, программе приходится угадывать, и сбитый порядок этому мешает.
Насчет отправки -- если используете порт 25, то попробуйте 587 (без шифрования или со STARTTLS), т.к. 25 часто блокируется. Или SSL + 465. Если подключение блокируется где-то как-то Интернет провайдером, и т.д., то дело все-таки не в программе.