After quite some time testing and research, I finally found MDL-16919, where it was stated that uppercase letters are not allowed in the usernames, no matter what (so not a bug, but a feature ;))
Can we please modify the lang string for this info on Site Policies?
Current: Allow extended characters in usernames: Enable this setting to allow students to use any characters in their usernames (note this does not affect their actual names). The default is "false" which restricts usernames to be alphanumeric lowercase characters, underscore (_), hyphen (-), period (.) or at symbol (@).
Based on whatver is written now, one can falsely assume that if the setting is enabled, then Uppercase letters will be allowed. Which is not the case. Users will be able to use any special characters #$%^, etc, but still NOT the uppercase letters in the usernames.