iPhone shows OS X Handoff of a device I want to remove
Handoff is keyed to your iCloud account, so you might want to sign in to https://www.icloud.com/#settings and see if that Mac is still listed. 

If so, there are links to what to do if the device is "lost, sold, gave away this device"

In a nutshell, sign out of iCloud entirely on that Mac. If that doesn't work, you can send a remote erase to that Mac which will erase everything on it - not just the Apple ID / iCloud settings.

Once you've ruled that out, you might need to sign out of iCloud on your iPhone, but I've usually been able to clean thing up from the Mac end of thing when I find unwanted entries like you have.

In your case overloading two user accounts and deleting one before signing out may have confused the registration. Can you restore that user account from a backup and sign out? If not, worst case is you might need to sign out from both (or even all) accounts on that Mac to remove the machine record from the cloud database.