Hmm, i did a little research into this, and i think i know what the problem was with my code. newRV is an alias for newRV_inc(), which means the item being referenced has an implicit SvREFCNT_inc() called on it, thus in the snippet i showed *hash ends up with a refcount of 2 instead of a refcount of 1. Changing it to newRV_noinc() should fix it.

    HV *hash = newHV();
    SV *type = newSVpv("string", 0);
    if ( NULL == hv_store( hash, "type", 
          strlen("type"), type, 0) ) 
    {
        SvREFCNT_dec( type ); /* free the SV */
        printf("hv_store failed\n"); 
        exit(1); /*me wonders about this...*/
    }
    XPUSHs(sv_2mortal(newRV_noinc((SV *)hash)));
[download]

I really have to get myself set up to check this, but I thought id mention it. BTW, if you havent already read it you should review "Reference Counts and Mortality" in perlguts. Which on a quick reading basically agrees with what i said before, with the minor caveat about newRV_noinc(), which it specifically documents as being a common mistake.

For example, imagine you want to return a reference from an XSUB function. Inside the XSUB routine, you create an SV which initially has a reference count of one. Then you call newRV_inc, passing it the just-created SV. This returns the reference as a new SV, but the reference count of the SV you passed to newRV_inc has been incremented to two. Now you return the reference from the XSUB routine and forget about the SV. But Perl hasn't! Whenever the returned reference is destroyed, the reference count of the original SV is decreased to one and nothing happens. The SV will hang around without any way to access it until Perl itself terminates. This is a memory leak.

Which basically explains why my original snippet "leaks like mad". It leaks like mad because the root of the structure that you want to disappear on its own never goes to 0, so the whole lot stays in memory. Change the newRV() to newRV_noinc() and it should be freed as and when expected and no leaks.