.htaccess url encoding

Hi,
I tried hard to find out solution but no success. I have put together this code in .htaccess:

Rewritecond %{THE_REQUEST} ^[A-Z]{3,9}\ /index\.php\?([^\ ]+)query=(.*?)&([^\ ]+)start=(.*?)&([^\ ]+)\ HTTP/
Rewriterule ^index\.php$ http://subdomain.domain.com/%2/%4? [R=301,L]

RewriteRule ^([a-z]+)/([^/]*)$ /index.php?parameter=0&query=$1&anotherpar=1&start=$2&lastpar=-1 [L] 

Working perfectly...but! If there is some diacritics in a address (query parameter), it fails. E.G.: If there is href to:

http://subdomain.domain.com/index.php?parameter=0&query=�&search=1

when someone clicks it, redirection fails. In browsers address bar it shows

http://subdomain.domain.com/%25C5%25A1%25C4%258D%25C5%2599

Does anyone now a solution how to make it working with european diacritics?

(BTW, what does this htaccess do...url from search engine like

http://subdomain.domain.com/index.php?media=0&query=money&search=1

changes to:

http://subdomain.domain.com/money

and it is actually not only rewrite, but it is 301 redirect, too)