I was also having the same problem over the last few weeks with one of my Linux mail servers and it really stressed me. From my research, note these:-
- Having/not having reverse DNS records does not contribute to an IP being blacklisted
- Changing your server's IP and then the MX records is just running away from the real problem
- Most spam generating spyware/malware rarely ever sends out mail through your mail server; your network/router is NATting for a host that's doing spamming on it's own.

The solution is initially to clean up your network. Note that normal anti-virus programs even when up to date rarely arrest spamming applications. You need a good anti-malware; try Spyware Doctor

Also consider deploying a firewall with a rule that only allows your server's IP to be the only host allowed to send out mail; i.e. a rule that allows outbound SMTP traffic (port 25 and 587 in some instances) from the server only.

Hope that helps you.

Regards,
Martin Mugo

On Tue, Jun 29, 2010 at 2:40 PM, Nawaz Bagha <nawazb@gmail.com> wrote:
had something similar in our office... ask your ISP to change your IPs.... and then redirect any AX/MX records to the new IP... And try getting an outgoing mail scanner e.g. Brightmail Gateway... Run a spambot check on the endpoints on your network as well.... 

--
NB

On Tue, Jun 29, 2010 at 1:57 PM, ibtisam jamal <ibty.jamal@gmail.com> wrote:
The blacklisted IP is a virtual IP and not the mail servers IP.
Recently there is alot of outbound traffic to the internet almost
nearing the download.



On Tue, Jun 29, 2010 at 1:41 PM, Edmund Okumu <edmund.okumu@gmail.com> wrote:
> Ask your ISP to do for you a PTR record; mail domain against Public IP. Then
> go to all sites blacklisting you and whitelist. Some learn from others so if
> you get whitelisted from others it will take a few days to come out of all
> lists.
> Also like they said ensure your network is clean brother.
>
> On Tue, Jun 29, 2010 at 10:23 AM, ibtisam jamal <ibty.jamal@gmail.com>
> wrote:
>>
>> Hi ,
>>
>> My public IP's are being blacklisted ....How do i go about it.
>> _______________________________________________
>> Skunkworks mailing list
>> Skunkworks@lists.my.co.ke
>> http://lists.my.co.ke/cgi-bin/mailman/listinfo/skunkworks
>> ------------
>> Skunkworks Server donations spreadsheet
>>
>> http://spreadsheets.google.com/ccc?key=0AopdHkqSqKL-dHlQVTMxU1VBdU1BSWJxdy1fbjAwOUE&hl=en
>> ------------
>> Skunkworks Rules
>> http://my.co.ke/phpbb/viewtopic.php?f=24&t=94
>> ------------
>> Other services @ http://my.co.ke
>
>
>
> --
> Edmund C. O. Okumu
> P.O Box 8490-00200,
> Nairobi, Kenya.
> TEL: 254-721-734935
>
>
> _______________________________________________
> Skunkworks mailing list
> Skunkworks@lists.my.co.ke
> http://lists.my.co.ke/cgi-bin/mailman/listinfo/skunkworks
> ------------
> Skunkworks Server donations spreadsheet
> http://spreadsheets.google.com/ccc?key=0AopdHkqSqKL-dHlQVTMxU1VBdU1BSWJxdy1fbjAwOUE&hl=en
> ------------
> Skunkworks Rules
> http://my.co.ke/phpbb/viewtopic.php?f=24&t=94
> ------------
> Other services @ http://my.co.ke
>
_______________________________________________
Skunkworks mailing list
Skunkworks@lists.my.co.ke
http://lists.my.co.ke/cgi-bin/mailman/listinfo/skunkworks
------------
Skunkworks Server donations spreadsheet
http://spreadsheets.google.com/ccc?key=0AopdHkqSqKL-dHlQVTMxU1VBdU1BSWJxdy1fbjAwOUE&hl=en
------------
Skunkworks Rules
http://my.co.ke/phpbb/viewtopic.php?f=24&t=94
------------
Other services @ http://my.co.ke



--
Regards,
NB...

_______________________________________________
Skunkworks mailing list
Skunkworks@lists.my.co.ke
http://lists.my.co.ke/cgi-bin/mailman/listinfo/skunkworks
------------
Skunkworks Server donations spreadsheet
http://spreadsheets.google.com/ccc?key=0AopdHkqSqKL-dHlQVTMxU1VBdU1BSWJxdy1fbjAwOUE&hl=en
------------
Skunkworks Rules
http://my.co.ke/phpbb/viewtopic.php?f=24&t=94
------------
Other services @ http://my.co.ke