This is what I have discovered from here:

Binding against the AD has a serious overhead, the AD schema cache has to be loaded at the client (ADSI cache in the ADSI provider used by DirectoryServices). This is both network, and AD server, resource consuming - and is too expensive for a simple operation like authenticating a user account.

While it does not explain the behaviour of why the try-catch does not catch the error, it did point me to a workable solution using PrincipalContext instead.

This works without any delay or error:

private bool AuthenticateUser(string userName, string password)
{
    using (PrincipalContext context = new PrincipalContext(ContextType.Domain, "EnterYourDomain"))
    {
        return context.ValidateCredentials(userName, password);
    }
}