how to delete a phone FOREVER in Microsoft's device list?

There's probably a driver in Device Manager that also needs deleting. I would try running Uwe Sieber's Device Cleanup tool to get rid of associated drivers in DevMgr for the phone you no longer have. Once you've done that, you can then delete it from the Device List (Devices & Printers) and it shouldn't come back. If that doesn't work, check out the method explained in this MS answers thread.
HTH,
--Ed--

#2 That did not work. It is not on the PC or the laptop after deleting it from my account, but I think "something" sync it back. So maybe there after all IS something on the PC after deleting it in my account.
Neither the laptop or the gamer has any device listed in devicemanager about the old phone (not in hidden devices either) nomatter if I has deleted it in my account or not.

EDIT: I have now tried to take the laptop with me home from work, and I tried to log in at My account at Microsoft at both computers at the same time. I then deleted my old android phone on BOTH PC's. Well, it was gone. I rebooted both PC's, and the old android phone was still gone. 2 hours later I'm at job again, logging in on my laptop just to see .... the old android phone is back yet again!! What the h.... is going on? Why is it next to impossible to get rid of an old phone in WIndows 10?? Please help!

I have read and followed this guide from Microsoft:
If you're planning to sell or gift your Windows 10 device or your Xbox One console, make sure you've removed all personal info from it.









Remove a device from your Microsoft account

---

After you've backed up and reset your device, you should remove it from your Microsoft account. Here's how:

• Go to https://account.microsoft.com/devices, sign in, and find the device you want to remove.
• Select Show details to see info for that device.
• Under your device's name, select More actions > Remove.
• Review your device details, select the box for I'm ready to remove this device, then select Remove.

You can then unlink the device from your Microsoft account so it doesn't affect your Microsoft Store device limit:

• Sign in with your Microsoft account at https://account.microsoft.com/devices.
• Find the device you want to remove and select Unlink.
• Review your device details and select Unlink.

Well, point 4 in the above does not show up, just the "Are you sure" and then the remove buttom.

@Burgurne: thanks for posting your solution. Odd and interesting, like so many of the gazillion other details about Windows 10.
--Ed--