Attack, thanks for that suggestion of making sure those ports were open. The thing is, file and printer sharing already works on this machine, so those ports already were open. I double checked in WF.MSC and made sure they were enabled for both Private networks and Domain networks (the network it's active on is a private network). After a reboot, still didn't fix the issue.

As for the registry entries I listed above as "working" - I seem to have been wrong. The problem returned today, despite those registry entries.

So, still stumped by this one.