It is normal that you find this rule1 "unnatural". It is entirely artificial and has no logic. It is considered artificial by most grammarians of the French language nowadays (including Grevisse).
The agreement with the preceding past participle with avoir was introduced into French in the 16th century (by Clement Marot) a French Renaissance poet, who was deeply influenced by the Italian language that had a similar agreement with the preceding direct object. But the rule was not made compulsory until the 19th century and it has had its opponents ever since. And it is considered French school children's worst nightmare.
Here's an article that sums it all up nicely and gives several references.
And another one that deals more with the logics of this "rule" and its psychological implications when teaching (French) children.
When you say this rule is "supported primarily by the fact that it's taught in school, and would die out if not for that." you are entirely right, and it is one of the features of French grammar that lots of people would like to do away with, it is the object of endless discussions2.
Excerpt of the Dictionnaire de pédagogie by Ferdinand Buisson (1901) in which he proposed a reform of French spelling :
La règle d'accord enseignée actuellement à propos du participe passé construit avec l'auxiliaire avoir a toujours été plus ou moins contestée par les écrivains et par les grammairiens. Peu à peu elle s'est compliquée de plus en plus ; les exceptions sont devenues de plus en plus nombreuses, suivant la forme du complément qui précède le participe, suivant que le même verbe est employé au sens propre ou au sens figuré, suivant que d'autres verbes accompagnent le participe. En outre, elle tombe en désuétude. Il paraît inutile de s'obstiner à maintenir artificiellement une règle qui n'est qu'une cause d'embarras dans l'enseignement, qui ne sert à rien pour le développement de l'intelligence et qui rend très difficile l'étude du français aux étrangers.
The rule concerning the agreement of the past participle with avoir that is taught nowadays has been always more or less opposed by writers and grammarians. Various additions of exceptions have made it more complex over the years [...] besides it is now becoming obsolete3. It seems useless to artificially persevere in maintaining a rule that is a cause of embarrassment to education, that does not help developing intelligence and makes the learning of French very difficult to foreigners. (Translation's mine)
Concerning the edit in your question, you can roughly say that one can hear the gender agreement when the past participle ends with a consonant4. And it is only since the 18th century (Modern French) that the final e has become silent. Before that it was sounded and it can still be sounded for literary purposes (eg in poetry, in a song) when necessity arises to have a rhyme or certain line length.
1 Accord du participe passé avec avoir.
2 Just one found in a quick google search.
3 Let's not forget he was writing at the beginning of the 20th. century at a time when not as many people could attend school as we do nowadays.
4 See this answer on French Stackexchange.