Our L2TP server (running Windows 2008 RRAS) is behind a NAT firewall. I've already verified that it is passing NAT-T. The firewall rules are all set up correctly to pass GRE, IKE, L2TP and there are no custom IPSEC policies running on the server. L2TP is using a PSK instead of a certificate. Oddly, my Windows 7 and 8 desktops cannot make a successful connection, but my iPhone and iPad devices connect successfully. I can't think of anything else to check.
Also note that we can use PPTP and SSTP just fine.
I have firewall and netmon logs for both the failed and successful connections. I've seen a lot of cases where iOS devices cannot connect where full desktops can, but this is the opposite and I can find no clues on the interwebs.
Update: I've even replaced the server in question with a fresh Windows Server 2012 installation and it still has the same problem.