If you use per-queue message TTL, then message expires and get removed from queue from head to tail (in the same order they was published).
When you use per-message TTL, then messages removed from queue only when they reach queue head, so situation when expired messages still reside in the middle of queue is normal. Such messages will not be send to consumer, and will be deadlettered (or dropped), but due to strict FIFO nature or RabbitMQ's queues that will happen as written above, when they reach queue head and delay before removal may be greater than actual message TTL. For example, if there are two message, first with TTL=10sec and the second one with TTL=1sec, second message will be deadlettered also in 10sec while it stay after first one.
To deal with messages that has different TTL, common workaround is to declare few queues, each for messages with same TTL or almost same, say, with precision 10sec. Actual precision may vary while it very application-specific and somehow empirical value.
If you will pick separate per-TTL queues, use per-queue TTL rather than per-message TTL for ease of messages workflow and to prevent disambiguation of understanding what happens with messages. Developers after you will thank you for that.
To re-process messages after their TTL use Dead Letter Exchanges, but beware of cycled messages problem: if RabbitMQ broker detects that your messages workflow cycled (messages get published to same exchange with the same routing key after it was deadlettered from it), it will silently drop message.
