Passwords containing "!" are always wrong
In the comments, ce4 pointed out what was going wrong.

A space gets inserted automatically after each exclamation mark (and probably other sentence limiting characters like full stop, half stop or question mark too), resulting in an invalid password with a space char too much.

Whenever I enter an exclamation mark, I also enter the following character, use backspace twice and then enter the following character again. Seems to be the simplest solution yet.

Samsung should consider turning off these weird auto-complete stuffs in password boxes!