Simple L2TP/IPsec server not working (openswan, xl2tpd, Ubuntu, Windows)

Well, that was terrible.

I found the solution in the last place I would've looked: the client. Windows does not support IPsec NAT-T by default, which is used whenever the server is behind a NAT (as in this case). You have to add a registry key to enable this - see http://support.microsoft.com/kb/926179/en-us (still applies to Windows 8). Then everything just works.

How I found it: this post, which I in turn found as the second hit from Googling for openswan ipsec STATE_QUICK_R2: IPsec SA established transport mode ESP/NAT.

In ipsec.conf, left needs to be not your public IP, but whatever IP your server sees, so 10.252.194.250 in this case. That way it can "match" up a left/right side connection. Where left=you, and right=%any.