Of course it depends on your climate, but I second the Egyptian walking onions: really handy and super tough.
Jerusalem artichokes are incredibly productive. Be aware that wherever they are planted is basically where they will always be :
Rocoto chillies. Perennial high-altitude chilli. Gangly plant, almost 'viny'. Loads of fruity, yet hot pods like Chinese lanterns.
Garlic's a perennial if I forget one or two and leave them in.
Do herbs count as veges? Thyme, sage, chives, mint, Vietnamese mint, oregano, rosemary, bay..
Rhubarb's a plant we think of as a fruit rather than a vege; whatever I call it, my 'Glaskin's perpetual' produces fat red stems and giant leaves all year round
Most of my veges aren't actually perennials, but generous self-seeders. Parsnips, rocket, upland cress, siverbeet, lettuces, salsify, coriander and many more.