The problem statement needs much clarification. In particular:

1. "the Perl Mail module" doesn't tell us much. Specifically which module are you using?
   
2. Where are you sending from and to?
   
3. What are you using for an SMTP server? the modules typically work by connecting to an SMTP server, often defaulting to localhost. What's used in your case?
   
4. As another asked, what changed in DNS?
   

We like to help, but we're not mind readers.

--Bob Niederman, http://bob-n.com