Not that it really satifies me... but I did get something working... right after asking

Turned out the it does work when I decode using UTF-8 when I create the request. (And removing all the left over decodes and encodes scatttered in my code). Just don't get why this works. Decode seems to me the opposite of what I need.