My relearned lesson for the day: when Linux networking weirdness occurs in a NAT environment, remember to try MTU clamping.
Thanks to the comments by Justin and Sesse, I was fast-tracked to the core of the problems I have been experiencing since Thursday, MTU issues. What's worse (from my pov) is that I have encountered this issue before with the provider I had in Timișoara, but, since that ISP was using PPPoE and my current ISP in Bucharest doesn't, I never really made the connection. I even had a commented out iptables rule for MTU clamping in my firewall script.
The rule I am talking about looks like this:
iptables -t mangle -A POSTROUTING -p tcp --tcp-flags SYN,RST SYN -o $EXT_IF -j TCPMSS --clamp-mss-to-pmtu
or like the one I have been using (seems more logical to me):
iptables -I FORWARD -p tcp --tcp-flags SYN,RST SYN -j TCPMSS --clamp-mss-to-pmtu
Note that this is not a fix, but a workaround and the real problem is over-zealous admins or weird setups which think that banning TCP fragmentation (or the entire ICMP traffic) is a way to secure networks.
Once again, thanks to everybody who read and/or commented about my issue.
 Sesse told me that in his case there was a transparent proxy involved when he exeprienced MTU weirdness.