Block cipher mode of operation with beyond-birthday-bound security I am looking for block cipher modes of operation that are secure even when the number of blocks encrypted exceeds the birthday bound.
It is not a standard mode of operation and I do not know if anyone uses it in practice, but one option is double encryption using counter mode and a non-repeating counter. That is, doing $E_{k_1}(i) \oplus E_{k_2}(i) \oplus p$. The sum of two PRPs is a PRF with better bounds than one. The bound is basically $O(2^{2n/3})$  rather than $O(2^{n/2})$. See The Sum of Two PRPs is a secure PRF.

For example, with a 64-bit block size that means something like going from encrypting 32 gigabytes before attacker advantage to encrypting 32 terabytes instead.