After more testing and reading this node the problem seems to be CGI.pm.
Since finding out, I upgraded my CGI.pm from 3.39 to 3.49, but either CGI.pm's PUTDATA param has gone missing again or soemthing is wrong on my side. Still, binary files end up as garbled mess in the .parmaters and param parts of __QUERY_OBJ -- Can anyone explain this??

I've given up since, and replaced CGI.pm with CGI::Simple according to the above mentioned node, and - guess what - CGI::Simple properly parses out the $q->param('PUTDATA') parameter from the request and PUT finally works for me!