And lastly, since it's speed we're after, a C implementation can't hurt. This benchmarks orders of magnitude faster than anything seen yet. (Update: fixed memory leak)

use Inline C => <<'__EOC__';

SV *fast_c (char *original, char *chopped) {
        int counts[256] = {0};  /* each potential character */
        int ptr = 0;
        int buffer_size = 0;
        char *ret = NULL;
        int ret_ptr = 0;
        int error = 0;
        SV *retsv = &PL_sv_undef;

        while (original[ptr] != '\0') {
                counts[original[ptr++]]++;
                buffer_size++;
        }

        ptr = 0;

        while (!error && chopped[ptr] != '\0') {
                counts[chopped[ptr]]--;
                buffer_size--;
                if (counts[chopped[ptr++]] < 0) {
                        error++;
                }
        }

        if (!error) {
                ret = malloc(buffer_size + 1);
                for (ptr = 0; ptr <= 255; ptr++) {
                        while (counts[ptr]-- > 0) {
                                ret[ret_ptr++] = ptr;
                        }
                }
                ret[ret_ptr] = '\0';
                retsv = newSVpvn(ret, strlen(ret));
                free(ret);
        }

        return(retsv);
}

__EOC__
[download]

And then here's a C implementation of demerphq's "scanning" method, which doesn't rely on counting up letters. This one's even faster:

use Inline C => <<'__EOC__';

SV *scan_c (char *from, char *to) {
        int f = 0;
        int t = 0;

        int from_len = strlen(from);
        int to_len = strlen(to);
        int ret_ptr = 0;
        unsigned char fc, tc;
        int error = 0;
        SV *retsv;
        char *ret;

        if (!from_len || !to_len) return(&PL_sv_undef);
        ret = malloc(from_len > to_len ? from_len+1 : to_len+1);

        while(!error) {
                fc = from[f];
                tc = to[t];

                if (fc == tc) {
                        f++; t++;
                        if (to[t] && (to[t] != tc)) {
                                while (from[f] == fc) {
                                        f++;
                                        ret[ret_ptr++] = fc;
                                }
                        }
                        if (t == to_len) error = 1;
                } else if (!fc || (fc < tc)) {
                        ret[ret_ptr++] = fc;
                        f++;
                        if (f >= from_len) error = 2;
                } else {
                        error = 2;
                }
        }

        if (error < 2) {
                while(f <= from_len) {
                        ret[ret_ptr++] = from[f++];
                }
                retsv = newSVpvn(ret, strlen(ret));
        } else {
                retsv = &PL_sv_undef;
        }
        free(ret);
        return retsv;
}

__EOC__
[download]