Yes, only citizens of Windurst can get the portal charm, but as long as one person has it to open the door, anyone can get through the 3-mage gate. Of course, you can also have one of each mage to stand on the portals..... The gate is located by going to the East tower in East Sarutabaruta, then meandering through to the south west (there are "cracked walls" you have to go through) - it is close to Nana Migho's hideout, if you've done that quest.
The Rhinostery quests grant access through the Windy Walls entrance (north part of the zone, down a path into the "moat"), but that key item only allows the one person to get through. You also have to defeat a NM in Eld. Necropolis - Lich C Magnus (who also drops the Lilith's rod).