Make sure DNS is resolving to the correct address. Presumably it is, or you would have also posted that your mail suddenly stopped working. Still, just do a quick ping to your server name from outside.
It sounds like possibly some sort of external firewall issue. Most common cause of this problem is a broken NAT translation. Either the outside firewall gets a request on port 3389 (RDP) and changes it to another port when it forwards it to the internal server, or the firewall simply doesn't know what to do when it receives the port 3389 request and discards the traffic.
If you can RDP in from internal LAN, then it doesn't sound like a problem with the server or security updates applied to the server.
Can you clarify something though? Is it RDP from outside, or RDP from a different LAN, but still on the inside? (Like a different VLAN, or different building in same network?)
If it's inter-LAN connectivity, then definitely check DNS resolution. Might be that your DNS server is not resolving requests for your subnet, or that the entry for that serve has gotten botched up. Try connecting via IP instead of server name. (Also, try FQDN and not just hostname)