I am someone who had a lot of trouble with this, having no formal education in higher mathematics until very recently, and thus having to figure out what is meant by a "correct" proof all on my own. This is a topic that is close to my heart. Specifically your quote here
But I would say it happened organically. It would be the same way a native speaker grows up in their home country, hearing the language being spoken around them and gradually assimilating it themselves. This is NOT useful to a student taking their proof-based class who has to immediately learn to be 'fluent' in the language of proofs.
is very uplifting. I find that a teacher/writer not taking this difference into account was the primary barrier, so just by realizing this I think you are 90% of the way there.
For me, the process of learning how to write proofs took an enormously long time, and was extremely frustrating. I tried books like How to Solve it and other similar books, but they did not help me at all.
The issue for me turned out to be two fold.
These books focused on proof strategies (i.e. induction, contradiction, breaking down a problem into smaller cases, etc) and not mathematical foundations (i.e. formal systems, formalizing common number systems, consistency and "well defined"-ness, etc). Jumping into the former without the latter, to me at least, is like learning to swim without a pool to swim in. That is, without having seen a branch of mathematics built completely from scratch either through set theory, type theory, or any other mathematical foundation of your choice, your students will have no way of "hooking" their knowledge on to something tangible, and everything will feel extremely floaty and ad-hoc. Like you are just making up the rules as you go along.
These books did not touch on the practical and philosophical issues associated with proof. That is, they don't answer the important questions "How can we know that these formal symbols on a page actually represent what we want them to represent intuitively?". Another way of putting it is: "How do you formalize something that hasn't been formalized before? How do you go from an informal fuzzy ideas about laws of physics being the same for everyone to General relativity? How do you go from fuzzy ideas about a transformation being 'natural' to category theory?". This may not seem important for basic understanding, but if you are expecting them to learn proof techniques in a "non organic" way, then it is essential that they have these questions answered. The answers to these questions are what are often assumed as given; they are the essence, I think, of what is gained "organically" in the manner you describe. Without the answer to these questions, formalization will feel cold and unsatisfying.
I think there are several ways to mitigate these problems. But for me what finally made it all click was seeing two things, corresponding to the two points above
I saw the basics of Real Analysis built up entirely formally from the axioms of ZFC in Tao's introductory book on the subject. That is, he defines sets, then natural numbers, then uses natural numbers to define rational numbers, and then uses those to define real numbers. I can't overstate how helpful this was. I also saw Peano Arithmetic and set theory built up completely from the ground up in Type Theory and Formal Proof by Nederpelt and Guevers. This book indirectly taught me good formal "strategies" of proof.
I saw the historical evolution of basic topology from its
informal roots to its modern form, in Proofs and Refutations. This allowed me to see how we got to the level of rigor we have today, and more practically, how real research works in the real world.
I would look into these books if you haven't seem them for ideas about how to get this "organically" gained knowledge out of your head and into your student's head. I am not exactly sure how this could all be fit into a one semester course, but it really didn't click for me until I read all three books.
But the essence I think, is making sure that they have an example of the right way to make some mathematical theory completely rigorous, defining every term, proving every theorem, etc. And also making sure that they have a clear understanding of why this rigor is there, preferably through reference to the historical evolution of the theory and not artificially constructed examples. (e.g. Once upon a time there was no formal definition of a polyhedron, then chaos ensued, now we have topology, once upon a time there was no formal definition of a limit, then chaos ensued, now we have real analysis, once upon a time there was no formal definition of volume, then chaos ensued, now we have measure theory, the list goes on and on...)