Thanks for the advice, folks.

If there turns out to be in fact a Betreibung, or if one comes, I will do the Rechtsvorschlag right away. If that does not remove it from the Betreibungsregister then I will obviously sue to have it removed. So far my understanding is that there isn't any yet as I did not receive anything from the Betreibungsamt, so I will start by sending letters to the Inkasso company with proof of payment and requesting that they step away.

This whole talk about private credit registers has me concerned though. Other than the ZEK (which according to their web site is quite transparent and bound to laws to prevent false claims in your report) what other such registers are there in use that you know of?

Just an update for whoever was following this:

First thing this morning I got a printed Buchungsanweis at the bank showing that the original bill has been paid to the merchant. I wrote a letter -- in the most reasonable sounding German I could -- to the Inkasso company.

In the letter I declared that I only now received their letter because I was out of the country and it was not sent registered, and the original bill I received from the merchant claimed as the creditor was paid as soon as I received it, attaching the Buchungsanweis as proof, and thus request that they withdraw any Betreibungen against me as well as any registrations of debt elsewhere. I stated that if they believe I still have any debts related to my order with the merchant, they shall send a detailed bill with signed statements from the merchant to back it, and otherwise if I need to open a legal process to remove a Betreibung that was already filed and not removed by them right away, they will be held liable for all costs of the process.

I called the original merchant to clarify the issue. They said they will check it and call me back. As they did not call me back within a few hours I called them again and they said that it was a mistake as they missed canceling the claim with the Inkasso company, with whom they just clarified the matter and canceled the claim, so I should ignore the Betreibungsankündigung.

I believe the merchant that they clarified the matter, but I sent my letter registered to the Inkasso company, with a copy to the merchant, to make sure it is on the record (as the clarification with the merchant was just over the phone) in case they screw it up nonetheless or just try to play dirty with it.

Even though it was the merchant's mistake that they failed to cancel the claim, I find the Inkasso company's tactic of sending a threatening letter with a bill for an excessively inflated made up amount with no details should be illegal.

Send the merchant or Inkasso company a bill of your own, for the involved time etc.

If they do not pay, you can do a Betreibung yourself or send the claim to an Inkasso company.

Even if it would be reasonably accepted, I would not go through that hassle now if I don't need to. But I will sure keep the receipt from the post sending the registered letters, and if do I get any trouble from the merchant or the Inkasso company I may well send the company owner a bill for that (plus the involved cost then) with warning (and intent) of filing a Betreibung if they do not pay then.

Was it by chance an agency called "intrum iustitia"?
Here is a good link: Unfair payment demand - Legal question

No, it was another one -- AIS All Inkasso Service, with a post box in Wädenswil.
Probably just the same kind of villains though.

Thanks for the link.

In particular it's worth noting that according to the article linked from that thread, if I understood it correctly, even if a debt is real and the collection is legitimate, beyond accumulated interest the law does not permit slipping random amounts on top of it as "collection fees".