Well, there is more misbehavior in CGI.pm. For example, if we call
then $q->url_param contains the key "keywords", but the respective value is empty. That means that you can't pass a parameter named "keywords" via query string if you use $q->url_param. The value of the "keywords" parameter will just be overwritten by CGI.pm.
Due to the problems mentioned in this thread, and due to the problem described above, I dumped CGI.pm and now parse the query string myself (with the help of uri_unescape). My code is now working like expected.