Here's an article from Microsoft that describes the dynamic DNS process with their DHCP server: http://technet.microsoft.com/en-us/library/cc787034(WS.10).aspx
The stock behaviour of W2K and up is for the client to request the DHCP server register the PTR record on behalf of the client, and the client registers the A record itself. The DHCP server can be made to register the A record and the PTR record (including for pre-Windows 2000 clients that can't make DDNS registrations themselves).
There is an optional setting to have the DHCP server delete the A and PTR records when a lease is discarded. If the lease hasn't time-out, though, the records won't be deleted.
You absolutely should be aging and scavenging your DDNS zones. If you're aging and scavenging, this will eventually "purge". If you're not, it won't.
This Microsoft support article explains how to set the TTL value for DNS resource records registered by DHCP servers (originally in a hotfix, now just built-in to the OS): http://support.microsoft.com/kb/322989
To alter the behaviour of client computers in DNS registrations, have a look in Group Policy in the DNS Client node under the Network subnode of the Administrative Templates node of the Computer Configuration. In there, you'll find that you can force the clients to register their PTR records, rather than having it done by the DHCP server (if you so desire), and you can set the TTL on records registered by clients.
I'm not sure why this would suddenly start occurring. Some configuration had to change, but I'm at a loss as to tell you where. Start talking to your co-admins about any changes they might've made in the DHCP server configuration or in the group policy settings for clients' dynamic DNS behaviour.
I can't say I've seen the behaviour of multiple clients registering the same PTR record. That's odd. I'll have to defer to someone else on that. I will say that all of my reverse-zones are always AD integrated and require secure updates, but I don't know that that would have an effect on this.
In my experience, just having aging and scavenging turned on makes a world of difference in eliminating stale records. The default 7 day interval has worked well for me.
Please don't use the word propagation when you should be using the words cache and/or caching. Using the word propagation in relation to DNS caching only serves to "propagate" the misunderstanding that DNS records propagate, which they don't.
When referring to DNS caching, it's only relevant to systems that have those particular records cached, which most certainly is not very many in this case. I would find it very hard to believe that you're not recieving ANY email due to DNS record caching.
At any rate, it looks like the problem is a firewall issue, based on the fact that your tests seem to be indicating that you can't telnet to port 25 of your email server from the outside. Since you just changed your ISP and were allocated different ip addresses, I would suggest looking at the NAT configuration of your firewall to make sure you've got the correct external ip address NAT'ed to the correct internal ip address.
Best Answer
Let me edit this to be completely clear. Static A records and static IP addresses are two completely unrelated things. It is normal to have machines with static IPs have dynamic DNS A records. You should not change this unless you have a compelling reason.
You shouldn't have to do this. If legitimate records are being scavenged, then you have configured scavenging incorrectly. You should read this link. It's for 2003, but the concepts about scavenging and refresh intervals are unchanged.
If the IPs are static on the servers, then there's nothing more you need to do. A static IP is a static IP.
I think part of your misconception is that you misunderstand how DNS records are updated. Yes, you can have DHCP update your DNS records using the DnsUpdateProxy group, but this is bad bad bad and it's not the standard configuration, so unless you've explicitly configured this (which I'm betting you haven't), then that's not how it's being done.
By default, an computer will send a DDNS record update to its primary DNS server when the adapter received an IP address and each day after that. The adapter registers itself and the kind of record that is created is a dynamic one. If it is being scavenged, then either your scavenging window is too small or you need to shorten the interval at which computers register themselves.
Having a static IP and having a static A record are two completely different things. In almost all cases, you don't want to create static A records for hosts that self-register. You only want to do this for hosts that don't, like *nix servers on a DNS server that only accepts trusted updates from AD clients or for something like a secondary interface with a dedicated IP that's hosting a website.