I see. Inheriting from Decimal and overloading __hash__ is a way to solve your problem, but it's IMHO a shallow bug and worth reporting.

I just tried hash(D.as_tuple()) and it is blazing fast. I think that unless the official line is "don't touch decimal.py until X", this change to hashing would be useful and (AFAICT) harmless enough to fit in e.g. 2.5.2. To avoid incompatibilities, __hash__ could check for Overflow and only use .as_tuple for values higher than the previous maximum (keeping, unfortunately, __hash__ slow for values below).

Could the current status of Decimal be made a bit more clear? Are bug reports/patches welcome? Is bugging  Facundo or RHettinger welcome? :)

If getting __int__ a bit faster and able to convert sans huge strings is desired,  I've updated that old function (see below) and AFAIK it could be used to replace Lib/decimal.py/Decimal.[__int__,__long__]. It gets about ten times faster on best cases and is about as slow on worst cases (could be much worse if "long(rint_part + rdec_part)/exponent" is a STUPID thing to do, but seems easy to avoid). As the original __int__ optimizes str(Decimal._int) and doesn't split/check for substrings, using the same path should speed this up more. I can run the tests and benchmark it (next month...) if there's interest.

def dec2long(number):
    """ Convert decimal.Decimal to long (abridged, non-checking version)"""
    decimal_string = str(number)
    if "e" in decimal_string:
        radix, exponent = decimal_string.split("e")
    elif "E" in decimal_string:
        radix, exponent = decimal_string.split("E")
    else:
        radix, exponent = (decimal_string, 0)
    if exponent:
        exponent = int(exponent)
        if "." in radix:
            rint, rdec = radix.split(".")
            radix_decimal_part_len = long(len(rdec))
            if radix_decimal_part_len <= exponent:
                radix_as_long = long(rint + rdec)
                corrected_exponent = exponent - radix_decimal_part_len
                result =  radix_as_long * 10L** corrected_exponent
            else:
                result = long(rint + rdec) / exponent
        else:
            radix_as_long = long(radix)
            result = radix_as_long * 10L**exponent
    else:
        if "." in radix:
            radix_integer_part = long(radix.split(".")[0])
        else:
            radix_integer_part = long(radix)
        result = radix_integer_part
    return result

As a comparison, here's __int__ (abridged) from decimal.py:
    def __int__(number):
        """Converts self to an int, truncating if necessary."""
        if number._exp >= 0:
            s = ''.join(map(str, number._int)) + '0'*number._exp
        else:
            s = ''.join(map(str, number._int))[:number._exp]
        if s == '':
            s = '0'
        sign = '-'*self._sign
        return int(sign + s)