Alright, so I've tried what I think is everything.
A wired connection is impossible where I'm living, so I'm stuck with wireless through a DD-WRT router (firmware up to date).
I have forwarded all necessary ports, set a static IP, enabled uPnP... I used to have open NAT, but lately it has reverted to strict.
When I check my detailed NAT info, it tells me I am behind a port-preserving port-symmetric NAT.
Please help, as this is getting really old.