Where does a BasicReject with requeue actually go?

Explicitly answering for anyone who, like me, came to this question late and needed a non-"read the docs" answer:

When a message is requeued, it will be placed to its original position in its queue, if possible. If not (due to concurrent deliveries and acknowledgements from other consumers when multiple consumers share a queue), the message will be requeued to a position closer to queue head. - From Rabbitmq's official site - rabbitmq.com/nack.html – smc

To expand on this comment from the (currently) top answer using your example

I have a queue that looks like this:

5 4 3 2 1 <= head

And I consume message 1

Queue is now: 5 4 3 2 <= head

then do: channel.BasicReject(ea.DeliveryTag, true);

Your result will be the same as initial,

5 4 3 2 1 <= head

If you have only one consumer. With multiple consumers it may be possible for the following:

Initial: 5 4 3 2 1 <= head

Consumer 1 accepts message: 5 4 3 2 <= head

Consumer 2 accepts message while consumer 1 is processing: 5 4 3 <= head

Consumer 1 decides to reject and requeue, resulting in: 5 4 3 1 <= head

I'd say the answer is here, I'll quote a part:

Messages can be returned to the queue using AMQP methods that feature a requeue parameter (basic.recover, basic.reject and basic.nack), or due to a channel closing while holding unacknowledged messages. Any of these scenarios caused messages to be requeued at the back of the queue for RabbitMQ releases earlier than 2.7.0. From RabbitMQ release 2.7.0, messages are always held in the queue in publication order, even in the presence of requeueing or channel closure.

So we could assume that RMQ is implemented in that way the messages are not deleted form the queue (physically deleted) until they are ACKed, they may have a ACKed flag or whatever.