'Find My Mac' says that it is already in use, how to fully remove previous configuration?
I had this happen to me a couple of months ago.  I was perplexed, as you were, about what could be causing it.  I figured out the following, but as there's no information for this online it could be incorrect:


Find My Mac is tied to the serial number of your Mac
Find My Mac was partially enabled before iCloud was released
Since it was partially enabled, a previous MobileMe account could cause conflicts.


Again, I have no definitive proof for this.  But I got this notice on a fresh install of the operating system, only after upgrading my MobileMe account to an iCloud account.

So if I were you I wouldn't worry about it.  Most likely it's just a MobileMe bug that never got quite resolved.