I solved this problem in a rather unconventional way:
I had this problem after I installed two OSX version on my internal disk: One with 10.10 and one with 10.12. When booting into 10.12, "Find My Mac" would not work due to "Recovery partition required".
Using Terminal, along with "diskutil list" and "diskutil mount ..." to mount the recovery partition it listed, I looked into the "SystemVersion.plist" file of the now-mounted "Recovery HD" and realized that the recovery disk was for 10.10, not for 10.12, and that was the culprit.
So the task was to install a recovery partition specifically for 10.12. Since I had another Mac with 10.12 installed, I copied the recovery partition from that disk, using the free program iBored (of which I am the author), and then wrote it over the outdated 10.10 recovery partition. After a reboot, I was finally able to use "Find My Mac".
I admit that doing what I did requires quite a good understanding of how disks and blocks and partitions work. Otherwise, you either won't get far, or may even damage you disk's data if you happen to overwrite the wrong blocks.
But still, I wanted to leave this note here for others who want to troubleshoot this and understand what I am talking about. Good luck!