Steffen,
Thanks for the detailed steps.
Using steps 6-11, on a ArcGIS 10.1 final machine I can reproduce the issue.
Using a 10.1 SP1 machine (we havent released SP1, we're finalizing it right now), I cannot reproduce the issue - so we've fixed it.
My apologies for the inconvenience.
A question though - why do you need to copy the script and model tool to a custom toolbox?
If you want to control parameters (for example, you want to remove options from the feature choice list, or you dont want to expose the raster format parameter) you can run the tool from the system toolbox, and then during publishing modify those parameters inside the service editor. Just click the parameter name on the left hand side and change the Input Mode, or configure the Choice List options. Unless you're adding new values to the data extract format task, everything else you want to do should be configurable through the service editor.
I hope this will provide a suitable workaround till SP1.