CrmUserChecker for No Microsoft Dynamics CRM user exists with the specified domain name and user ID and The user ID associated with the current record is not valid

In your experience in CRM 2011, Have any problem with Create New User or login with user, but still said invalid, etc?

Or

This can be caused by :

1. The user was coming from upgraded CRM version and you were not mapping when you should map that.
2. Then the user can be disabled user and also you create new CRM User and that user will have two status (even though their user GUID are different, pas they are using same domain login name), they are Enabled and also Disabled

So, what you should do is to do query check your system user

select IsDisabled, FullName, CreatedOn, ActiveDirectoryGuid, DomainName from systemuser
where DomainName = 'CRM\aaa'‏

Then see whether return two or one entry.

Okay, for those who don't like to be hectic with SQL Coding,
You also can use CrmUserChecker Tool which is you can get from Microsoft when you contact for their support.

This tool is very useful.

And very informative, which is showing you that You have two entries of the same Domain Name in the SystemUser view.

It also can be problem solver when you execute this tool by clicking OK two times after pop up out to choose OK or Cancel.

Not only that, every single SQL Query if you are curious they also produce from their log :

It also gives you every detail of the Query to make you more understand and also gives you Diagnostic about the inputted user.

Hope it helps!
Thanks.