  Dense coding with non-maximally entangled states has been investigated in
many different scenarios. We revisit this problem for protocols adopting the
standard encoding scheme. In this case, the set of possible classical messages
cannot be perfectly distinguished due to the non-orthogonality of the quantum
states carrying them. So far, the decoding process has been approached in two
ways: (i) The message is always inferred, but with an associated (minimum)
error; (ii) the message is inferred without error, but only sometimes; in case
of failure, nothing else is done. Here, we generalize on these approaches and
propose novel optimal probabilistic decoding schemes. The first uses
quantum-state separation to increase the distinguishability of the messages
with an optimal success probability. This scheme is shown to include (i) and
(ii) as special cases and continuously interpolate between them, which enables
the decoder to trade-off between the level of confidence desired to identify
the received messages and the success probability for doing so. The second
scheme, called multistage decoding, applies only for qudits ($d$-level quantum
systems with $d>2$) and consists of further attempts in the state
identification process in case of failure in the first one. We show that this
scheme is advantageous over (ii) as it increases the mutual information between
the sender and receiver.
