Consider the attached two relevant papers. (The first paper is commented on, the link to which I also present below.)

http://journals.aps.org/prl/abstract/10.1103/PhysRevLett.73.1060

http://www.sciencedirect.com/science/article/pii/S0375960105005748

http://journals.aps.org/prl/abstract/10.1103/PhysRevLett.75.3020

The question is "allowed as what?" Anti-unitarily implemented symmetries like time reversal and transposition are not cp, but are perfectly ok as global symmetries. Only when you apply them to a subsystem leaving the rest of the world unchanged you get an inconsistency (failure of positivity).

A lab is always a finite part of the world, and indeed if you implement an operation by locally doable things, like adding independent ancilla systems, local unitary dynamics, and tracing out ancillas, you will necessarily get a cp operation.

The first paper mentioned by Behnam Farid talks about a different situation: a joint evolution of system and bath, for which sometimes the best ansatz for the initial state is not a product between the two. The answer given by Alicki clears this up nicely (3rd qute in that post).

Positive, but not cp operations play a role as entanglement witnesses. Using that such operations can still be represented as linear combinations (not with positive coefficients) of cp ones one can "measure" such operators by taking a corresponding linear combination of proper expectation values. But that is a much weaker form of "implementation", which equally well goes for negative operations. It is useful to keep that distinction clear, in the sense of "not allowing" such operations