Your post me made consider something: my iCloud account does not have an iCloud mail address associated with it. I never opted to create one. But for those that do have an iCloud mail address, is it required that that email be used for handoff to work?
The only way too have it working for me was to add an iCloud email. Just that.