Wow, I just got stuck on this one for about an hour or so, so writing this up so you don't have to waste time.

Here is the trick - have two different email addresses.

support@yourcompany.com - you will use this as the address that email is sent to by customers, and the address that you respond to cases from.

support2@yourcompany.com - this is a secondary email address that will only ever be used for email to Case.

You can NOT have the same email address set up to do Email to Case on Demand, AND use it for auto response rules, AND to reply from.

Set up Email to Case to use the support2@ email address.

In your email management system (eg Exchange or Google Apps) set up support@ to forward to the Salesforce created Email Services Address for support2@.

So incoming email goes from support@ directly to the SF Email Services Address set up for support2@ and then into Salesforce.

Now set up an organization wide email address as support@

Now, set up your Case Auto Response rules to use support@

Ensure the Email Template for the Auto Response rules have the Case Thread ID in the Subject and Body.

Now, the missing link that I missed - in your Case Feeds settings enter the support@ address as the sepecific email address to send from.

Now test it.

Email into support@
An auto email is sent back.
Reply to that email.
Ensure a new case is not created.

Browser not supported