This is the ebay auction I got the display from: http://cgi.ebay.de/ws/eBayISAPI.dll?ViewItem&item=251049844026 As you can see it looks different in the item description - that's China for you I guess 
Unfortunately it didn't come with a data sheet...
I reworked the code, included a delay of 0.5 s, but no change - but the problem is something else entirely as I just found out:
It's the power supply. I bought a 5V/1A power supply, which I used when I took the photo. Just now I connected the arduino to my computer to upload a sketch - and now it works perfectly!
I checked the voltage on the 5V Terminal of the arduino: When I use the external power supply I only get 3. something Volts there, which explains why the contrast of the display was so low. But the power supply does output 5V when nothing is connected, and when I power the display separately with the power supply it works as well (but then I don't have a common ground, plus I don't want to use two power supplies).
How can this be, the external power supply has more juice than a usb port, right? Is this a problem with my arduino?
Edit: Nevermind, should've read the data sheet of the Arduino more carefully: 7-12V for the power supply , but 5V operating voltage 