Found out why...
Finally after much sleuthing I put the pieces together and got to the bottom of this.
Turns out, the Mac that was appearing, was an old one of mine that I had sold on eBay. Now I am fairly anal about security, so I positively did a full reformat and secure erase of the drive, then reinstalled Mac OS before sending it out.
Here's where the problem comes in. Can't remember the exact version I reinstalled, but it was one that I had downloaded from the App Store. Apple confirmed, because of this, the OS was linked to my AppleID, and even after changing my password, or removing that machine, it will always continue to "phone home" as "my" device.
None of the other iCloud services are affected, so even though the new owners had logged in with their own AppleID, the computer continued to report location to my account.
Solution is for the new user to reinstall Mac OS from scratch with their own AppleID. They could also just deactivate the "find my mac" option, which will stop it from phoning home. Unfortunately, this involves getting in touch with the current owner which may or may not be practical.
Apple also pointed me to this KB for steps to take before selling your machine.
http://support.apple.com/kb/HT5189?viewlocale=en_US&locale=en_US