Even if putting a timestamp on packets is too expensive for each individual packet, there are ways to mitigate that.
For example, a queue manager could put a magic timestamp packet in it's queue at periodic intervals. Say, 0.1 ms. (This number may need tuning..)
Every time a timestamp packet hits the front of the queue all packets behind it until the next timestamp marker will be at least (timestamp + something less than 1 interval) old. If that timestamp is too old you just drop the packets in the interval and move on.
Of course this solution isn't as good as individual timestamps - you can still get into situations where you're sending very old packets because there are too many packets in the intervals that you ARE processing - but I can imagine cases where this type of tradeoff may be worthwhile.