Does frequent key change weaken encryption? Following scenario:
We are using OTR for communication between Alice and Bob which means after each successfull message exchange a re-keying happens for both parties leading to new AES-keys for the encryption and MAC generation.

Lets say Alice and Bob exchange 1000 message-pairs which leads to 1000 re-keying occurrences.

An attacker Mallory is able to record all messages between Alice and Bob.

Mallory brute-forces her way through the encryption by choosing one possible encryption key and trying it for every single one of the 1000 message-pairs.
Doesn't this lead to giving Mallory a better chance of cracking the code of one message-pair because she can use a single key and try this key for 1000 message-pairs (thus weakening the encryption)?

A little further thinking:
Using a single encryption key over a long period might increase the possibility of exposure of the encryption key. So re-keying is an effective means against that. But comming from the above example, re-keying too often might also lead to a weak encryption.
Is there a trade-off between the two of them?

I am not a crypto-analyst or any expert and I am well aware that my language propably doesn't fit into the crypto world by means of being to broad in some statements or not specific enough. I have no problem in understanding probility theory if an answer needs to include it, although I prefer pragmatism over theory.
Strictly speaking, it does make a brute-force attack more likely to recover a key for any message pair, but the impact of recovering a single key is minimized by frequent re-keying, since that key can't aid the adversary in decrypting any other messages. If you don't re-key, a brute force attack is only marginally more difficult but success gives you everything instead of just one message.