I have a plotting issue that is keeping me from progressing in my current story. It isn't a big thing, but for some reason I can't find my way around this without addressing it. So I figured I'd post here for the wonderfully creative insights that always manage to crystallize...

Background:
My current protaggynist (in epic fantasy genre) is falling in love with someone from another country/culture. He meets someone else from that country who tells him about a traditional food he is absolutely head over heels for. My protag finds/makes/steals said food to present to his love interest as a way of reminding her of her home, its kind of a Big Deal, and the story moves on.

What I want to know is: what food should I pick?

It can be a real or imagined food/ingredient/dish, but I am limited in what I can pick. Perhaps its the chef in me, but I want this to be something believable.

My current idea is a fermented sauce of fish parts (Garum, kind of like Worchestershire sauce) or a sort of maple syrup (derived from tree sap) that they cook meat in.

Some facts:

Her native country is an island, so they eat a bit of fish. But it isn't tropical, so no coconuts or mangoes or whatever.

I am thinking of making her vegetarian for other reasons, though this isn't fixed in stone... or even fairly damp clay...

I want it to be something obscure, so different from my protag's native dishes that he is surprised people eat it.

The two countries aren't that far apart, they share general climate and flora and fauna and stuff (think France and England)... though something exotic is certainly possible.

And, if it is addictive (as in those who use it have a physiological withdrawal when they stop consuming it) that would be a nice bonus. But not necessary...

There's two different directions you can go on this. One would be the fancier foods, the delicacies. If your character's lover is poor, delicacies may be something they've never tried, or only tried once or twice. There would be the excitement of eating something they've always longed for. The downside is because they haven't eaten it often it won't have that same nostalgia, and they may turn out not to like it at all, having the opposite effect that your character was hoping for. If they're rich and have eaten it often then there will be the nostalgia as well as the enjoyment.

The other direction is the simple, common foods. More high end and maybe something they would eat less often, but something they love. There would probably be larger portions, perhaps some varieties. Your character's lover would be very enthusiastic about this familiar food they probably haven't had in a while and have missed, as well as giving more intimate feelings of home and warmth and good memories. A possible downside if they're rich is that they consider it beneath them, even if they've eaten it often and enjoy it. It may end in the same type of disaster serving delicacies would be to a poorer person.

Some points about it:

My MC is pretty important in this world, so money is no issue. But what does matter is this third character he gets the food idea from. This third guy lived in the other country for many years and thus acquired a taste for this food himself. When he comes back, he keeps eating it and actually introduces it to the MC with the intention of luring the girl in (he's a bad guy. What can I say?) The MC doesn't know his intentions so he goes along with it.

Definitely liking the flower idea also... flowers are actually very symbolic in this story and this may be a good intro to why...

Flowers and herbs:

Nasturtiums taste peppery and are actually quite good in a salad (as well as being colorful).

Other edible flowers are calendulas, violas, pansies, and violets, lavender, borage, chamomile, English daisy, honeysuckle, lilacs, marigolds, mustard, dianthus, rosemary, roses, sage, scented geraniums, thyme

Vegetables:

Squash flowers and pea flowers (but not sweet pea flowers) are edible. So are raddish flowers (which taste a little like raddishes). Broccoli, chives

Fruits:

Apple blossoms, citrus, elderberry, strawberries

The trick with edible flowers is to know that they are grown properly. You don't want to eat flowers from a plant that's been treated with a systemic pesticide. Plus, there are very similar plants where one is edible and the other is not--peas and sweet peas, and saffron crocus (which produce the world's most expensive spice) and autumn crocus (which are poisonous). So there's some room for a mixup there, too.

There's a tree hereabouts known as Yaupon from which a potent tea is made. Ilex vomitoria leaves make a strong caffeinated brew. The berries are a potent emetic and which have a slight psychotropic effect.

Another local tree with leaves that taste like lemon yet numb mucus tissues is the Zanthoxylum clava-herculis, or toothache tree. Medicinal, some consequences, not particularly addictive.

About the only foods I know of with potential phsyiological habituation consequences I have to mind at the moment are nettles and fiddleheads. Oh, and Old World grain rusts like ergot. Though there are consequences, they're not especially addictive as they're often fatal.

Toadstool mushrooms, Amanita muscaria, the magic mushroom, habituation of a peculiar nature, abrupt withdrawal from gradually developed tolerance to strychnine and cyanide constituents may cause death; therefore . . .

Betel nut and coca leaves, not foods, per se, but socio-cultural rituals.

I think comfort can come from communal rituals as much as from privately consuming for mere sustenance.

Some ideas for consideration from which to create a food which fits the bill.

The hard-to-get part is relevant to your story, because if it's just a matter walking out into the forest and picking morels it's hardly a sign of fanatical devotion. You want your protagonist to have to scale the wall and steal the rapunzel from the witch's garden.

Sugar ant (Australia and Brazil)
Green ant paste (Australia, and tastes lemony)
Termites (Africa, only available one day every few months, when the queens and drones fly away)
Witchety grubs (Australia)
Mangrove worms (Australia, and you have to hack the wood to find them)
Bogut moths