Windows – Setting-up Windows Server 2003 as an L2TP/IPSEC VPN server

As noted in the update to the question, even with double NAT the VPN is working from a Mac to Windows but not Windows to Windows. It seems it's really only a matter of coming up with the correct search term to find a solution.

As per this KB article, on the Windows XP client machine we need to create a new DWORD value named AssumeUDPEncapsulationContextOnSendRule in HKLM\System\CurrentControlSet\Services\IPSec. For double NAT it needs a value of 2.

Now I need to find a solution for Windows 7, because it's inevitable that sooner or later I'm going to have to deal with that.

Update

For the benefit of anyone with the same issue, the fix for Windows 7 is to create a new DWORD value named AssumeUDPEncapsulationContextOnSendRule in HKLM\SYSTEM\CurrentControlSet\services\PolicyAgent. Again, for double NAT it needs a value of 2.

Windows 7 has some different settings from Windows XP which can affect compatibility; the most notable ones are the removed support for the MS-CHAP V1 authentication protocol (only MSCHAP V2 is supported) and different encryption settings for L2TP/IPSEC (as documented here).

I don't know how this applies to Ubuntu, but maybe it can point you in the right direction.