I know that the modulo operation for negative values is not well defined, but I would at least expect that the result is the same no matter if you use ints, floats or decimals. However Decimal seem to behave else than the builtin types.

Python 3.1.2 (release31-maint, Sep 17 2010, 20:27:33) 
[GCC 4.4.5] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from decimal import Decimal
>>> -3 % 5
2
>>> -3. % 5.
2.0
>>> Decimal(-3) % Decimal (5)
Decimal('-3')
>>> 

I could reproduce the same for python 2.6.6.

I believe that this was a deliberate design decision, though now that I look it seems it's not well documented.  That should probably be fixed, so I see this as a documentation issue.

More details:

The specification on which the decimal module is based requires that there be a 'remainder' operation with the semantics of Decimal's '%' operation (i.e., the result of x % y has the sign of x).  However, the specification doesn't say anything about how the prescribed operations should map to language constructs.

So the choice was between (1) leaving '%' for Decimal objects unimplemented, and providing a separate 'remainder' method, or (2) mapping '%' to Decimal's remainder operation, and accepting the slight mismatch between the '%' semantics for float and Decimal.

Perhaps the wrong choice was made.  But it's there now, and to me it's not so obviously wrong that it's worth the upheaval of deprecating '%' for Decimal objects.

Of course there's a third choice, which is to implement the float % semantics for the Decimal type;  however, this is outside the scope of the specification---none of the specified operations matches this behaviour, and I'd oppose the addition of such an operation to the Decimal module.  There's a strong sense in which Decimal's % is a more natural operation for floating-point types than float's %.  (For one thing, it's exact in many circumstances, while float's % suffers from surprising results with negative operands.)

Reclassifying as a documentation issue.

The doc change should also note that // and divmod suffer from a similar mismatch:

>>> Decimal(-2) // Decimal(3)
Decimal('-0')
>>> -2 // 3
-1
>>> -2.0 // 3
-1.0

However, the invariant that x = x // y * y + x % y is retained, as it should be.

Here is a patch that adds an explination for the difference in the behaviour to the FAQ section of the Decimal documentation.

New changeset 290f3b75480f by Mark Dickinson in branch '2.7':
Issue #12005: clarify behaviour of % and // for Decimal objects.
http://hg.python.org/cpython/rev/290f3b75480f

New changeset 0ec314f26791 by Mark Dickinson in branch '3.2':
Issue #12005: clarify behaviour of % and // for Decimal objects.
http://hg.python.org/cpython/rev/0ec314f26791

New changeset f626c214cad0 by Mark Dickinson in branch '3.3':
Issue #12005: merge doc patch from 3.2
http://hg.python.org/cpython/rev/f626c214cad0

New changeset 0263d2ef9530 by Mark Dickinson in branch 'default':
Issue #12005: merge doc patch from 3.3
http://hg.python.org/cpython/rev/0263d2ef9530

Docs updated.

Mark, there's a small typo in the patch: "preseve the usual identity"

D'oh!  Thanks.

Typo now fixed.