In my experience, journals do not care much about co-first authors (and similar). And why should they? As long as there are no authorship disputes or gift authorships, this simply does not affect their process. The only exception is that they have to insert another footnote on the authors or a sentence in the author contributions in typesetting. I have not seen a journal that explicitly forbids marking authors as co-first and I cannot imagine a reasonable journal rejecting a paper on the grounds that it does not want to accommodate co-first authorship.
As for corresponding authorship, its meaning strongly depends on the journal and field; so it makes sense to first find out what it means for this journal. However, if this is something you can assign, I assume that here the corresponding author is the author who can respond to inquiries on the paper after publication.
I would assume that the journal you contacted simply misunderstood what you wanted or the person who handled your request was clueless. Therefore, I would simply submit the paper as regular and if the submission system does not allow for it, include a note on how you want authorship to be assigned. If they refuse, briefly explain this. If they still refuse, face-palm, and go to the next journal.
Or to answer your titular question: Unless your field is very weird in this respect, it should be rare that a journal refuses co-first authors. If it does not explicitly state this on its website, I would not worry and simply submit your paper with a short note about how authorship should be.
