I just submitted a paper to some journal. Since they didn't specify a template, I used the IEEE template. Unfortunately, they immediately rejected my paper because they think I already submitted the same paper to one of the "IEEE Transactions" journals. I know for sure that's not the case. But how I can prove to them that my paper is not submitted to another journal. Is there a database for a list of submitted papers?
If I understand you correctly, they thought it was a double submission because the template you used included the header "IEEE Transactions on ..."?
Email the editor and explain that there has been a misunderstanding. If you make it clear that you only used the template because there was no template specified and you liked that one, a reasonable editor will probably at least remove you from their blacklist, unless they have other reasons to find your submission shady. They may or may not agree to consider your submission after all.
As a side note, "IEEE Transactions" is not even a journal. There are many "IEEE Transactions on <Topic>". If the template really only said "IEEE Transactions" you could note this in your explanation.
Of course no such database exists - it would be an incredible breach of review secrecy if people could look up what papers I currently have under review.
That said, the much more important question is why you even have this problem. A journal would never assume that a paper is already under review elsewhere without a strong reason. Maybe one of the reviewers reported the paper as double submission (I have done this in the past when I received two very strongly related parallel submissions).
Even if you really are innocent and they just jumped to this conclusion based on the template, there is nothing to do than to move on. A journal can choose to reject your paper for any reason or no reason at all. You can of course contact the EiC and clarify, but if they don't believe you, you don't really have a recourse other than never submitting there again.
There is no such thing as "submitted paper database".
There is also no method to prove that you did not submit the paper anywhere else - the journal relies on your (signed) statement "I did not submit the paper to any other journal.". If the journal still rejects the paper on this ground without providing any evidence for this claim, this is a red flag. The only thing you can do is to approach the editor and certify again that the paper has not been submitted anywhere else.
I can imagine that the journal may have some guidelines on formatting (but no template) and that your paper would not have been rejected if it would have been formatted according to the guidelines. (It may look weird to use a template specific for one journal but submitting to another, though. On the other hand, many people use AMS templates for preprints…).