Restoring it, takes an average of 3,8 times more memory than disk space => ca. 1,2GB!

This is not surprising --- Storable may store the data more space-efficient than it is in the RAM --- think of malloc overhead, necessary struct alignment, and the size of a SV*.

Saving is weird, after all the 330MB have been saved, store takes another 2200 seconds of 100% CPU time on a P3 1,26GHz even after the complete file is already on disk.

Maybe it's the global destruction which is causing the slowness. This may be due to an inefficient malloc. For example, it was reported that on FreeBSD, perl with the system malloc is very slow on deleting a large hash. Similar is true for certain Linux' malloc versions.