I fixed the strangely conditional segfaults. I had omitted one of the mysterious macros--or rather only used it once instead of twice.

int callComp( SV* cmp, SV* a, SV* b ) {
    dSP;
    int rv;
    ENTER; 
    SAVETMPS; 
    
    PUSHMARK(SP);
    XPUSHs( newSViv( SvIVX( a ) ) );
    XPUSHs( newSViv( SvIVX( b ) ) );
    PUTBACK;

    if( call_sv( cmp, G_SCALAR ) != 1 )
        croak( "Bad comparator" );
    SPAGAIN;

    rv = POPi;

    PUTBACK; // << Was missing and is required!
    FREETMPS;LEAVE;
    return rv;
}
[download]

But I'd still gratefully receive any suggestions from all those XS aware onlookers?

I'd also appreciate it anyone who's done callbacks using Inline::C, could show me how the above sub would be coded in terms of the Inline_Stack_* macros?