I found the problem.
Images are requested as: http://server/_media/imagefile.ext?w=100&h=200
Note that there is a question mark before w=100.
Then, the rewriting converts the /_media/imagefile.ext?w=100&h=200
to => /lib/exe/fetch.php?imagefile.ext?w=100&h=200
Note that now, the question marks are two - thus the query string is no longer valid.
When dokuwiki tries to get the variables, everything after the second question mark is erased from the QUERY_STRING.
So, $_REQUEST['w'] gets a blank value and the images are always returned in their highest resolution.
I am not sure which is the best solution to this problem.
EITHER the images will have to be requested in another way (instead of image.ext?w=100 => image.ext&w=100)
OR, dokuwiki (in fetch.php) should use the REQUEST_URI and split stuff on the fly instead of using the $_REQUEST array.
I am using php 5.3.2.