Dill can go to seed and come back the next year. I have it here, growing out of cracks in the concrete. Coriander is another that can resead. Not many herbs can live in very cold climates of winters, but I did have good luck with thyme. It was started from seeds indoors in pots, last spring and then planted outside in June. It turned purple color all winter and now is back to a deep green with lots of tiny white flowers. It should be a permenent plant eventually. Suggest that you read through the herbs forum as there are many threads mentioning the same cold hardiness of herbs.

Yes, Thyme, also Chives, Greek Oregano, Lemon Balm, some mints, Catnip are a few that come back for me here.
I've had annuals Chamomile and Cilantro reseed here also.

Thanks for everyone's help. I really am only looking for culinary herbs but you are right about medicinal herbs and such. She is a good gardener but tends to opt for mostly annuals and thus usually spends (imo) too much money on them. I'm slowly trying to introduce herto perennials and she loves to cook and garden. I think the "organic" aspect of the cooking herbs would appeal to her because 7 years ago they became a organic farming operation...

I always like to suggest roses for herb gardens. They were important parts of any antique herb garden. Roses offer fragrance, beautiful blooms, and tasty hips (wonderful in tea). Design-wise it will add some structure and interest to the garden.

Garlic is a perfect companion plant for roses - the herb garden needs an allium or two. Garlic and chives are just two members of the allium family and you should be able to find an extra hardy variety or three that can survive the zone.

Don't forget some annual plants like chili peppers which are pretty and useful!

FataMorgana

Here is a link that might be useful: Midwest Hardy Roses

Most hard neck varieties of garlic are well suited for very cold climates. Usually they get planted in late summer, early fall, for the following years harvest in early summer. Mine have just had their 'scapes' removed and will soon have dieing leaves, which indicates that they are ready to be dug up.

I have had good luck with sage in Northwestern Wisconsin. I am trying tri-color this year for ornamental value. I also suggest pansies. The flowers make a great garnish and have little flavor. Happy gardening.

Don't forget French Tarragon, sorrel, salad burnet, chervil*, and parsley. *annual