Exchange 2003 spam and NDR's

I have a client with about 25 users on a Server2003 env with Exchange 2003 server.  They are very heavy email users and also get a ton of junk mail, I have Symantec Mail Security installed and also the IMF build into Exchange SP2.

Here is the problem...
With the amount of junk mail they get the outgoing mail queue was getting jammed trying to send NDR's to the junkmail senders, I thought of turning off the NDR's for badmail but when I did so I got the warning that this option may increase the amount of junkmail since it would make the server respond differently to bad email address and therefor make the Spammers able to determine if an email address is valid or not.  So I left the default setting.

My solution was simply to use my customers ISP (Rogers Cable) SMTP server as a smart host, this seemed to have solved the problem until recently.  

However, Rogers has outsourced their email servers to Yahoo and Yahoo has recently instituted some emial caps.  Since all the outgoing mail is sent to the rogers smarthost and requires authentication from Yahoo's perspective all 25 users are sending email through 1 account and Yahoo has labeled teh account as a smammer and disable outgoing email on that account.  The Rogers cannot reset this nor can they tell me what the cap is.

So can I go back to using DNS to look up mx records and send our own mail and trun off the NDR's for bad mail or is there another simpler solution?

Thanks