@Alex, just like Steve and Wash, you hit the nail on the head. RDNS on incorrect host.
 
@Michael should correct this or get AK to change to current name and problem resolved.
 
Haiya @Michael, chai na mandazi.. :-)))))  ( just kidding...... but see what the gurus on the list came up with in a matter of minutes. It did not take long to get to the root of the problem. This list has some crazy talented people. Hakuna mchezo )
 
Long Live Skunks! :-)
 
 
2009/11/19 Alex Nderitu <nderitualex@gmail.com>
Muchai,s explanation is right, the only other explanation is that AK servers could have been relaying (after their MXs receive the emails from the Internet) to the wrong POP/IMAP servers.

rDNS actually exists;
akamiru@akamiru:~$ host 41.215.59.106
106.59.215.41.in-addr.arpa domain name pointer mail.pasicoea.com.
akamiru@akamiru:~$ host mail.pasicoea.com
mail.pasicoea.com has address 41.215.59.106

Only problem is the configured hostname on the server, pasico-east-africa.com should be mail.pasicoea.com.