What a wondrous thread! There is SO MUCH priceless information here about what is edible and where it grows. May I share? I've two related books, "Edible Perennial Gardening" by Anni Kelsey, and "The Minimalist Gardener" by Patrick Whitefield. Both books reference some perennial vegetables (sea kale, Daubenton's kale, sea beet, etc.) which I'd be hard-pressed to find in my area (sw Ohio) but many of the plants grow on multiple continents. Here are the more or less permanent edibles in my 50' x 25' yard:
Hablitzia tamnoides (Caucasian mountain spinach, perennial) I just planted these seedlings out for the first time this spring. Hope the slugs don't find them.
Allium cernuum (Nodding wild onion)
Allium tricoccum (Ramps) - they are not in an ideal spot and have been languishing - will divide and move to a shadier/woodsier spot. The leaves have a very intense garlic/onion flavor.
Common garden chives
Corylus americana (American hazelnut) (Five years old, no nuts yet)
Lindera benzoin (Spicebush) - the berries from this can be dried and used as seasoning.
Mountain mint (teas!)
Marsh Mallow (the actual plant - roots used for tea)
Viburnum opulus (Cranberrybush viburnum a.k.a crampbark) (I've not sampled the berries which are edible but can cause stomach upset raw. Also recently discovered that its bark has medicinal properties. I've not tried it out yet. The "bush" has gotten immense!)
And the self seeding volunteers
Purslane (a slightly tangy, fleshy leaf with a lot of Omega-3)
bittercress (like other cress, slightly peppery)
dandelion (Harvest roots in early March or before they start trying to flower for best taste. I cook and eat them, and they remind me of artichokes with a somewhat bitter aftertaste. Wait too long to harvest, and they are bitter as can be, but still OK for teas. The greens are also best in March, )
Hopi red dye amaranth (young leaves in salad, mature leaves in soups/cooked, and I think the seeds are edible as well)
rustic arugula (sylvettica)
Currant bushes would be nice, as I adore currants, both red and black!
Have considered, but not planted, chokeberries (Aronia melanocarpa) for the berries (have to cook to make edible, plus the plant suckers/forms colonies) and pawpaw trees a.k.a. Michigan banana (Asimina triloba) for the fruit (need maybe 2? plus the critters would definitely get these before I do!). Actually there are quite a few native plants that I'd plant if it weren't for the size or the suckering/colonizing habits. The yard is too small!
I love perennial veg, but don't have nearly enough. Here's my experience in my humid continental Midwest climate z5a. Asparagus is a perennial favorite (especially Purple Passion) so I've got about 60'. Walking onions have become a staple guild plant that tolerates shade, competes against grass, prolifically propagates and makes great early green onions. Caucasian Mt Spinach grows easily, tolerates shade, modestly self-seeds, early growth is good in a mixed salad, older cooked like spinach, I'm a fan. Nettles are a wild harvested favorite, I find it a tender and mild green and have transplanted some into the timber by the house. I save the cooking water and dilute cold mint (and other) teas 50/50 and the kids don't notice. I just discovered several patches of ramps in the timber too and am very excited, they don't taste especially garlicky to me but the greens have a very rich savory flavor. My 3 year old sea kale plants were healthy but resented being transplanted and died (I still have some seed and need to experiment more). Out of 25 or so perennial kale I grew (Experimental Farm Network) a few years ago, only about 4 survived the first winter (it was a test winter -26F) and those remaining didn't survive last winter (a mild one, -12F), but they weren't well cared for so I should try again as they were good eating and we love kale (and perennial greens are my holy grail).
I was surprised that Wild arugula (random packet of sylvetta sp.) perennialized in the greenhouse (along with a few parsley plants that persisted for 4-5 years despite going to seed each year). Horseradish is a bulletproof perennial, and though one can only eat so much horseradish sauce, it's leaves make a pretty mild, acceptable cooked green. But unlike hybrid comfrey it propogates by seed as well as root fragments so keep it far from your garden.
My favorite tea is anise hyssop (Agastache foeniculum). The best is from "native" seed I harvested from a restored prairie nearby, far better than any of the half dozen "improved" varieties I've grown (granted only one or two were selected for their aroma). I've also run across A. nepetoides in the woods and field edges but have never tried it as tea. If only sacred basil was perennial in my climate!
The common daylilies have decent buds and flowers though I've never bothered to harvest in quantity and bring into the kitchen, maybe they'd be good battered and fried? I haven't tried hosta yet. Sunchokes are decent. I usually ignore in the fall and forget in the spring, but next year! I'm most interested in trying Linden, Turkish broccoli, perennial kales/greens, groundnuts and maybe a super hardy bamboo.
PS - Many mentioned berries. Here are some lesser ones I appreciate: honeyberries (shade tolerant! early ripening, many varieties, easy to propogate from hardwood cuttings in early spring, tasty if a bit fiddly to harvest, they turn color well before they're prime). Gooseberries as well as red/white/black currants are tasty and shade tolerant so they don't take up prime real estate and go in the understory.
Quail Seeds in California has Hablitzia (under the name Caucasus Mountain Spinach), Good King Henry, two kinds of sorrel, Erba Stella, Lovage, perennial arugula, perennial clumping onions, and more. www.quailseeds.com
Asteraceae-Asteroideae-Heliantheae: Rudbeckia laciniata (sochan, Green-headed Coneflower, Common Cutleaf Coneflower, Green Coneflower, Goldenglow)
It sprang up in an area that has pretty damp ground and is somewhat shady for me here in Piedmont North Carolina, and due to pets, not a place where i want edibles. I transplanted it last fall to my food plot and nibbled on some greens this spring. Next year i hope to really dine on it.