What is the largest number of blocks a transaction has ever waited for confirmation?
This is not a full answer, but a partial answer somebody may use as a stepping stone to craft a complete answer.

E.g. blockchain.info shows both "received time" and the time of the block a transaction was included in. 

It appears to me that the "11 minutes" in the "Included in Blocks" time for this transaction corresponds to the difference between "Received Time" and "Block time" of the first confirmation.

If this information is available on blockchain.info's API, someone could parse all transactions to find the maximum.

By additionally evaluating the fee of a transaction in comparison to fee levels at that time, and confirmation times of each input of the transaction, the additional constraints of this question could be addressed as well.