It turned out that the problem was only with new users which were created by code. Further investigation revealed that there was the cause was a missing home directory. Windows has troubles with importing a certificate (with priv key) to a user without its profile directory already created, hence "Internal Error".
The solution was to force creation of the home directory for all new users created by code.