I've written some deep test including a deep EXR exporter and viewer to explore the data structures.
If one right, they are actually not that heavy, since multiple samples only need to be stored for pixels that actually consist of different surfaces/objects in the first place.
However, you certainly need to process more data and can't use many of the shortcuts available for flat images. It's also quite expensive (but possible) to change the sample count of the image during a processing operation.
And yes, that other package is slow as a snail dealing with them (I was really surprised when I tested it) - but then it seems to be quite slow in the first place.
Having said that, the advantages far outweigh the disadvantages. I'd love to see proper deep images implemented. Heck, I'd even help if required.
Cheers,
Mike