this is NOT normal in my opinion.
Which authentication method is configured for this particular Web Application ? I imagine NTLM but just to be sure :)
If only NTLM is selected, have you performed any enhancement / restriction in this sense at domain level concerning NTLM ?
The SharePoint farm is provisioned in the same domain as the end user or is it using a dedicated resource forest ?
It will be nice to know if this behavior is there since the beginning or if it popped up at some point