It is not intended to "last forever," but you are supposed to completely "remove" the system from iCloud/Find My Mac before disposing of it. As you discovered, simply re-installing the OS doesn't do it.
Sadly, I think the only way to reliably fix it would be for you (mentaluproar) to be on the system (via "GoToMyPC" or similar,) log in to iCloud on it, enable "Find My Mac," then disable it and log back out.
Apple makes it clear on iDevices that you need to disable iCloud/Find My iPhone before transferring the device, but isn't so obvious with Macs.
Sadly, I think the only way to reliably fix it would be for you (mentaluproar) to be on the system (via "GoToMyPC" or similar,) log in to iCloud on it, enable "Find My Mac," then disable it and log back out.
Apple makes it clear on iDevices that you need to disable iCloud/Find My iPhone before transferring the device, but isn't so obvious with Macs.