TL;DR: Decide based on whether your CURRENT form includes an enclosed payment, and not based on whether your original Form 1040 filing had an enclosed payment. For Form 843, that usually means sending to the address where you would send a return without an enclosed payment.
Background
The city that you file for the case "And you ARE NOT enclosing a payment use this address" has the actual service center. The address to which you file the tax return is not the actual street address of the service center; you can get these street addresses on the IRS website. But it's the same city. In particular, the IRS has service centers processing individual tax returns in Kansas City (MO), Austin (TX), and Fresno (CA). You can also get a full list of IRS service centers here, including ones that do not process individual tax returns.
The city where you file for the case "And you ARE enclosing a payment use this address" does not have an IRS service center. In particular, there are no IRS service centers in Louisville (KY), Cincinnati (OH), San Francisco (CA), Cincinnati (OH), and Hartford (CT).
The reason that tax returns with payments need to be sent to a separate location (without a service center) is that the payment processing is done separately at that location. My understanding is that after the payment is taken, the rest of the tax return is then forwarded to the corresponding service center. That is why the IRS tells you not to staple or paperclip payments with the rest of your tax return.
For instance, for California taxpayers, those not enclosing a payment should file to a Fresno address, and those enclosing a payment should file to a San Francisco address. But the IRS has a service center in Fresno and doesn't have a service center in San Francisco.
Relevance to your case
Therefore, the relevant criterion for deciding where to file is not the location where you originally filed your tax return, but rather, whether your current form has an enclosed payment. Since Form 843 is not usually accompanied by a payment, a case like yours most likely involves sending your form to the service center directly (i.e., the "And you ARE NOT enclosing a payment use this address" column address).
The IRS does not explicitly provide Form 843 filing addresses but it does provide filing addresses for Form 1040X, which has a somewhat similar role of making or seeking corrections. Note that the addresses listed for this are the same as the "And you ARE NOT enclosing a payment use this address" column addresses for Form 1040, i.e., the cities that have IRS service centers.
Thus, for the example of California, you would file Form 843 (or Form 1040X) with the Fresno address and not the San Francisco address, as long as your Form 843 (or Form 1040X) is not accompanied by a payment. This would be the case even if your original Form 1040 was filed with the San Francisco address because that form included an attached payment.
