By the later Middle Ages, spice had come to mean "something expensive from far away." Due to their distant origin, they were perceived as dried powders from the beginning. What we would see as flavorful food additives easily accessible and grown in Europe, like garlic, would be classed as herbs or vegetables: green and fresh (even if more commonly used once dried). And on the other hand, Europeans went nuts for a spice they called tutty: the scrapings of soot from chimneys in Alexandria, Egypt.

Two special cases demonstrate the importance of both "from far away" and "expensive" in determining what was considered a spice. Saffron actually grows in Europe, but was marketed as a spice (sold by apothecaries, etc.) due to how ridiculously expensive and time-consuming it was to grow and harvest. Meanwhile, pepper had qualified as a spice once upon a time, but by the 15th and 16th centuries it was so ubiquitous in Europe that it was viewed as "rustic," which is medieval for redneck. If peasants could afford it, the rich didn't want it.

I'm fascinated by how Europe developed a really ambivalent relationship to this necessity of spices being almost unobtainably expensive. On one hand, you can actually watch the justifications/reasons for the high cost of spices evolve over the late Middle Ages as Europeans gained better awareness of the Indian Ocean trade.

At first, Europeans convinced themselves that spices in the west were so expensive because they were incredibly rare in the east. Travelers like Marco Polo--and the popularity of their travel accounts as literature--kind of killed that idea with their revelations (exaggerations) of incredibly abundant spices in places like, y'know, the Spice Islands. The next step was to justify the high prices because, despite their abundance in nature, spices must be hugely difficult and intimidating to harvest. Venomous snakes infesting the fields were a common explanation here. Finally, as more and more merchants from the West ventured east and western interest in the natural world grew--and western governments started levying heavier taxes on merchants trading spices in Europe--Italian and Portuguese merchants in particular began to argue that the high prices were due to the markup from Arab middlemen.

And then on the other hand: instead of just blaming Arabs for keeping prices high, the merchants started arguing that they could lower the cost of spices by traveling directly to the Indian Ocean themselves! (Sound familiar, America?)

And just what were Europeans doing with the scrapings of Egyptian chimneys? As you note, spices were used as medicines above all, and also preservatives; likewise distilled into perfumes and cosmetics, burned as incense, and--yes--heavily added to foodstuffs as flavoring. Their "exotic" origin, as vaguely "from the East", only added to the allure and desirability. There was a whole mythology of religious transcendence and connections to paradise that sprung up around spices. (Even medieval Islam, which unlike medieval Christianity and Judaism did not use incense in its religious services, developed a tradition of heaven smelling "spicy.")

By the end of the Middle Ages, spices had become one of the ultimate luxury consumer goods, as useful for their social symbolism as actual properties. If you were wining and dining the glitterati of Florence, you best be serving exquisitely, intensely spiced dishes at all your meals!

Best source here is Paul Freedman, Out of the East: Spices and the Medieval Imagination.