Checking Inconsistencies between Users and Contacts Emails (via civicrm_uf_match table ?)
The civicrm_uf_match table is the correct place to look.  I can't explain why you're seeing what you're seeing!