The answer about carbon configuration was in the right direction, however it did not explain why the things never showed up, even not in the Graphite Browser, which should take the cached data into account.
The actual cause was different, after some looking at configuration files, I found the following, which probably is more related to my problem:
> # Softly limits the number of whisper files that get created each minute.
> # Setting this value low (like at 50) is a good way to ensure your graphite
> # system will not be adversely impacted when a bunch of new metrics are
> # sent to it. The trade off is that it will take much longer for those metrics'
> # database files to all get created and thus longer until the data becomes usable.
> # Setting this value high (like "inf" for infinity) will cause graphite to create
> # the files quickly but at the risk of slowing I/O down considerably for a while.
> MAX_CREATES_PER_MINUTE = 50
This actually explains why sending lots of new measures to statsd did only create some, but in random order... It depended on minute-switchover for new measures to be actually created.