A friend is running a VPS (CentOS)

His business partner was the sysadmin but has left him high and dry to look after the system. So, I've been asked to help out in fixing an apparent spam problem. His IP address got blacklisted for unsolicited mail. I'm not sure where to look for a problem, but I started with netstat to see what open connections were running. It looks to me like he has remote hosts connected to his SMTP server. Here's the output:

    Active Internet connections (w/o servers)
Proto Recv-Q Send-Q Local Address               Foreign Address             State      
tcp        0      0 78.153.208.195:imap         86-40-60-183-dynamic.:10029 ESTABLISHED 
tcp        0      0 78.153.208.195:imap         86-40-60-183-dynamic.:10010 ESTABLISHED 
tcp        0      1 78.153.208.195:35563        news.avanport.pt:smtp       SYN_SENT    
tcp        0      0 78.153.208.195:35559        vip-us-br-mx.terra.com:smtp TIME_WAIT   
tcp        0      0 78.153.208.195:35560        vip-us-br-mx.terra.com:smtp TIME_WAIT   
tcp        1      1 78.153.208.195:imaps        86-40-60-183-dynamic.:11647 CLOSING     
tcp        1      1 78.153.208.195:imaps        86-40-60-183-dynamic.:11645 CLOSING     
tcp        0      0 78.153.208.195:35562        mx.a.locaweb.com.br:smtp    TIME_WAIT   
tcp        0      0 78.153.208.195:35561        mx.a.locaweb.com.br:smtp    TIME_WAIT   
tcp        0      0 78.153.208.195:imap         86-41-8-64-dynamic.b-:49446 ESTABLISHED 

Does this indicate that his server may be acting as an open relay? Mail should only be outgoing from localhost.

Apologies for my lack of knowledge but I don't work on linux in my day job.

EDIT:
Here's some output from /var/log/maillog which looks like it may be the result of spam. If it appears to be the case to others, where should I look next to investigate a root cause? I put the server IP through www.checkor.com and it came back clean.

Jun 29 00:02:13 vps-1001108-595 qmail: 1309302133.721674 status: local 0/10 remote 9/20
Jun 29 00:02:13 vps-1001108-595 qmail: 1309302133.886182 delivery 74116: deferral: 200.147.36.15_does_not_like_recipient./Remote_host_said:_450_4.7.1_Client_host_rejected:_cannot_find_your_hostname,_[78.153.208.195]/Giving_up_on_200.147.36.15./
Jun 29 00:02:13 vps-1001108-595 qmail: 1309302133.886255 status: local 0/10 remote 8/20
Jun 29 00:02:13 vps-1001108-595 qmail: 1309302133.898266 delivery 74115: deferral: 187.31.0.11_does_not_like_recipient./Remote_host_said:_450_4.7.1_Client_host_rejected:_cannot_find_your_hostname,_[78.153.208.195]/Giving_up_on_187.31.0.11./
Jun 29 00:02:13 vps-1001108-595 qmail: 1309302133.898327 status: local 0/10 remote 7/20
Jun 29 00:02:14 vps-1001108-595 qmail: 1309302134.137833 delivery 74111: deferral: Sorry,_I_wasn't_able_to_establish_an_SMTP_connection._(#4.4.1)/
Jun 29 00:02:14 vps-1001108-595 qmail: 1309302134.137914 status: local 0/10 remote 6/20
Jun 29 00:02:19 vps-1001108-595 qmail: 1309302139.903536 delivery 74000: failure: 209.85.143.27_failed_after_I_sent_the_message./Remote_host_said:_550-5.7.1_[78.153.208.195_______1]_Our_system_has_detected_an_unusual_rate_of/550-5.7.1_unsolicited_mail_originating_from_your_IP_address._To_protect_our/550-5.7.1_users_from_spam,_mail_sent_from_your_IP_address_has_been_blocked./550-5.7.1_Please_visit_http://www.google.com/mail/help/bulk_mail.html_to_review/550_5.7.1_our_Bulk_Email_Senders_Guidelines._e25si1385223wes.137/
Jun 29 00:02:19 vps-1001108-595 qmail: 1309302139.903606 status: local 0/10 remote 5/20
Jun 29 00:02:19 vps-1001108-595 qmail-queue-handlers[15501]: Handlers Filter before-queue for qmail started ...

EDIT #2
Here's the output of netstat -p with the imap and imaps lines removed. I also removed my own ssh session

Active Internet connections (w/o servers)
Proto Recv-Q Send-Q Local Address               Foreign Address             State       PID/Program name   
tcp        0      1 78.153.208.195:40076        any-in-2015.1e100.net:smtp  SYN_SENT    24096/qmail-remote. 
tcp        0      1 78.153.208.195:40077        any-in-2015.1e100.net:smtp  SYN_SENT    24097/qmail-remote. 
udp        0      0 78.153.208.195:48515        125.64.11.158:4225          ESTABLISHED 20435/httpd