Share and Manage Watchers auto-complete return inconsistent results

There doesn't seem to be any particular rhyme or reason to when the user auto-complete field in the Share and Manage Watchers dialogs will show certain users. A customer raised a support case where they can add a particular user to the Manage Watchers page fine, but when trying to share that exact same page the auto-complete on the Share dialog says "No matching user or email found".

I've been able to reproduce similar behaviour in a local install.