The list of devices that have been tested (and are supported by Microsoft) with OMA can be found at http://www.microsoft.com/exchange/techinfo/outlook/owa_mobile.asp. To get support for all these devices, you need to install the latest available 'Device Update' (see link) on your Exchange Front-End server. Microsoft continuously releases new Device Updates adding support for more devices.
The Nokia 6820 mentioned above is not on the supported list. This can mean it was never selected to be tested, or that Microsoft couldn't make it work well with OMA. It indeed sounds strange that the username input field for Basic Authentication would be limited to 16 characters.
The Nokia 3650 mentioned above is on the supported list, but only if you have installed the most recent DU (Device Update). You could try looking in the Event Log of your Exchange server to see if there are any OMA events giving more information than the end user error message.