@estel: Sorry for not coming up with a solution; the update however has some additional debugging info enabled, so if you start 'presencevnc' from the command line you will get some info on what keys were pressed and what presence VNC actually sent to the server. Maybe you could send me an excerpt with some of the broken characters in it?
Also, do polish characters work if you type them on the built-in keyboard or on-screen?

I tried looking at rDesktop, but the bluetooth keyboard option only adds some special handling to some specific keys like F5, does enabling the option actually make a difference?

If all fails, typing the text in the maemo editor, copying and pasting it on the remote machine might work. (at least it bypasses all the mess about keycodes)

@aRTee: Try setting the quality to high before connecting, I don't think it makes use of the missing library. (Though it won't be much fun over the internet...)