Phone not appearing in Android Device Manager
Well, I don't seem to have an answer why this was happening, but I got some advice about how to finally fix it.

From Ryan Lestage on Google+:


Clear data for the following apps:


Play Store
Download Manager
Google Services Framework

Restart your phone. 
Fire up the Play Store app.
Wait for the device to show again on the web Play Store. It will appear under Settings &gt; Devices. It may take a half-hour to several hours to appear.


When your phone has shown up in the Play Store with the date registered as today's date, proceed with the next steps, but not before. 


Open Google Settings from your device's apps menu.
Touch Android Device Manager.
Uncheck Allow remote factory reset.
Go to your device's main Settings menu, then touch Apps &gt; All &gt; Google Play services.
Touch Clear Data. Note that this action doesn't remove personal data.
Go back to Google Settings and select Allow remote factory reset.
Restart your device.﻿


I would like to know exactly which of these steps was the magic sauce, but I'm content that it worked at all. I suppose that Play Store connection makes some sense, because while my phone was listed there, it showed a "Last Used" date back in March or somesuch.

I really hope that the setting sticks this time, and that I won't be forced to repeat this process every couple of months just to protect my device. (If so, I'll go back to some of my other options, like Carbonite and/or Lookout.)