Probably an example of wrong error message from ADE. Most of their error messages are just confusing, but they like to throw a misleading one in the mix sometimes to keep users on their toes.
It is probably semi-authorised.
Try ctrl-shift-D (cmd-shift-D on Mac) while running ADE in Library view, to remove any existing authorization or semi-authorization.
Try again to register with your Adobe ID.
I appreciate your suggestion, however this didn't work. Any other ideas?
Just checking: when you did the ctrl-shift-D did it come up with some dialog like 'Are you sure you want to erase this computer's authorization'; and did you check 'confirm' to that?
If not, try again.
Another possibility is to install ADE 1.7.2 instead and try on that. It is more reliable than ADE2.0 in various ways.
Version 1.7.2, it is a little difficult to find, available on Adobe site for Windows and for Mac.
The forum software is sometimes corrupting the link above. There shouldn't be a blank in 'editio ns.html'. The following redirects to the same page: http://tinyurl.com/diged172
And answering your first question: Isn't that the point that the devices you use use the same ID? Yes, absolutely. And it is possible when things work properly.