Nokia Messaging has a nasty "bug". Breaks down like that:
When you register a Nokia Messaging account on the device itself, your account details will be the same as the first email address you would like to poll with it. Now, Nokia Messaging has a password policy, the password has to be of a certain complexity. If the password for the email account you would like to configure doesnt match the complexity Nokia Messaging wants, you can't setup the account. A corrupted account gets setup respectively. Why?

To poll the email account, address and password of the account has to be provided. If password isn't good enough for Nokia, a faulty Nokia Messaging account will be created which cannot be used. If you provide a strong enough password for Nokia Messaging, which doesnt match your accounts password, a faulty Nokia Messaging account will be created which cannot be used because of the password not matching your account password.

Workaround: email Nokia about this and let them remove the insufficiently passworded and thus faulty Nokia Messaging account from their database. Once removed, set a stronger password for your (Gmail)account and recreate the account in Nokia Messaging.

The way I got it done: I didnt want to wait for Nokia to clean up the database, so I tried a different approach. If you have several email addresses and anyone/some of them is suffisingly passworded, use that account in Nokia Messaging. After you have a working Nokia Messaging account, you can add any insufficiently passworded accounts you like. Example: 2 accounts, 1 Hotmail with strong PW, 1 Gmail with simple PW. On the device, register a "Hotmail-Nokia-Messaging" account using the strong Hotmail password. Once succeeded, add your "insecure" Gmail account to Nokia Messaging later.
So my Nokia Messaging login is user@hotmail.com and this account polls, at the same time, my hotmail and my Gmail account. And the Gmail password I never changed. Got an email reply two weeks later though, the account has been purged from the database