How to avoid automatic responses from putting our mail server in a loop?

Not allowing more than 'X' messages between 2 parties in one day.

Almost right, now consider how fast automatic responses happen as opposed to legitimate messages; if you implement a flood limit, you will allow typical messages while not allowing rapid flooding because of automatic responses.

So, set up "X messages per Y minutes" or something along those lines.

in addition to the "limit x amount of messages in y amount of time per address" there are a few indicators that a message is automatically generated and should therefore probably not be forwarded.

check for example the following headers (and SET THEM in your mail forwarder as well, so well behaving out-of-office implementations don't even reply to your application)

precedence: bulk/list/junk
x-precedence: bulk/list/junk
auto-submitted: auto-replied
X-Auto-Response-Suppress: ALL/DR/NDR/RN/NRN/OOF/AutoReply
x-autoresponse

also, some out-of-office implementations do not use the user email as envelope sender but something like postmaster@ or the null sender.

I listed a few more indicators in this stackoverflow question but I'm not sure they apply in your case.

More information would be great, but in the absence of that I will assume you can do whatever you please. I'm also going to assume that these auto-replies quote the message they respond to.

As such, assuming your volume and computing power allow this, why not look for repeated responses in the ABAB pattern? That is, if you see the following, bounce it back with a kind message saying that the similarity of responses is like that generated by automatic responses:

From: Adam
Sent: Wednesday, January 03, 2013 9:10 AM
To: Box Co
Subject: RE: That thing

I'm on vacation and will get back to you on January 10.
-Adam

From: Box Co
Sent: Wednesday, January 03, 2013 9:11 AM
To: Adam
Subject: RE: That Thing

We are closed in order to observe the Tamaseseri Festival and will return tomorrow.
Box Co
Where the boxes are best!

From: Adam 
Sent: Wednesday, January 03, 2013 9:10 AM
To: Box Co
Subject: RE: That thing

I'm on vacation and will get back to you on January 10.
-Adam

From: Box Co
Sent: Wednesday, January 03, 2013 9:08 AM
To: Adam
Subject: RE: That Thing

We are closed in order to observe the Tamaseseri Festival and will return tomorrow.
Box Co
Where the boxes are best!

From: Adam 
Sent: Wednesday, January 03, 2013 9:07 AM
To: Box Co
Subject: That thing

Do you have that thing I put in the box?
-Adam

Do something along the lines of /\nSubject.*\n([.\n]*?)\nFrom/ to find what each party sent to each other and compare for sameness in the ABAB pattern. You'll have to remove the effects of auto-indenting etc.

This is not a simple solution, but I believe that it could be made to work and should minimize false positives and false negatives.