Block cipher birthday bound and a KDF workaround
Obviously you assume blocklength is $128$ bits. I believe the following is correct.

One might try rainbow table TMTO attacks, assuming known plaintext, and succeed with time and memory complexity somewhat better than
$$
O(2^{(2/3)k})
$$
where $k$ is the effective keylenth,
against such a scheme but it would be secure beyond the birthday bound.