Windows – Secure Remote Desktop to Windows Server 2008 R2 from Windows XP

To summarize the rambling below: How do I connect (using Remote Desktop Connection) from Windows XP SP3 to Windows Server 2008 R2 (or Windows 7) without clicking the checkbox on the server that says Allow connections from computers running any version of Remote Desktop (less secure)?

So, I've discovered that newer versions of Windows have "more secure" versions of remote desktop on them, that requires network level authentication to work securely. Unfortunately, Windows XP RDC doesn't support NLA, and the the intertubes have surprisingly little to say about actually making it work without clicking the checkbox that says Allow connections from computers running any version of Remote Desktop (less secure). Now I don't really consider "use the less secure version" to be an acceptable answer ("What's that, can't make ssh work? Yea, I solved that by just using telnet instead."). Upgrading to Windows 7 is not an acceptable answer either, cause while I agree that Windows 7 is "pretty darn cool", it isn't all that practical to tell other people in my organization "just go upgrade" when they want to connect securely via RDC to a particular system.

Even Server Fault seems to come up with very little to say on the topic, which really surprised me (the closest I could find was this question, which was almost there, but not really). It amazes me how many admins are perfectly willing to click the "less secure means it will work" button, so I went on a hard target search of every hen house, dog house, and out house on the intarwebs to find the answer. After days of searching I came up blank (ok, maybe it was more like 20 minutes, but it felt like days). So I started drafting this question on SF, got distracted, and never posted it.

Today I came to finish the question, applied a little more google-fu before doing so, and stumbled upon the answer, which I'm recording here for posterity (although I'll wait like 20 minutes before posting the answer in case one of you out there already knows it, so you can have the credit and gain the rep for a correct answer).