Middle Ages gave us crucial inventions that built European civilization (mills, windmills, agriculture inventions like three-field system, ships building technology and so on), also we have got well developed philosophy - especially scientific methods of reasoning and logic, that were cornerstone of all later science development.
How it was possible without writing?
Middle Ages life was simply not writing/visual oriented, it was based on speaking and listening and in no way people lost ability to think because of that. For instance PhD thesis was presented as a lecture followed by discussion.
When people wanted to "sign" something they were exchanging or giving some symbolic item (like a ring) and that's all. That's why various saints relics were so popular then, they were symbolizing people's affection, etc. Or people were just signing, as most people could write their names even though they could not write as we understand it today - despite many believes people in Middle Ages were quite educated, including "Third Estate", that is "the Peasantry", more, typically they were going to the same schools as rich people kids, the only difference was that rich people had to pay for the school.
I really recommend "Lumière du Moyen Age" ("Those Terrible Middle Ages!: Debunking the Myths") by Régine Pernoud, it nicely describes a really rich, open and dynamic culture that didn't really need writing.