I'm currently implementing such an undirected graph. I haven't gone towards adding weights to the connections, but my approach so far has been to have the gates as "places" in the current zone, with a distance between the current player position and the gate. Each gate connects to its own arrival place in another zone. These connections can have zero or a minimal weight, and should work well enough with A* once I get to add routing through the mesh.

I'm not sure if having two unidirectional connections instead of one bidirectional connection adds problems further down the path. So far, I haven't found any problem with this approach and for me it makes things like zone wide events easier, as these events can be tied to the arrival place.

That sounds almost exactly what I'm looking at. Each zone has a series of jumpgates in 3D space that link to another jumpgate in another zone. On first glance you'd think that you'd just represent each zone as a node in the graph but then you'd come to realize there's no way to calculate the non-zero distance between gates in the same zone.

You doing yours for a game of sorts or something completely different.

Well, it's a "game", except that it's a game framework that I've implemented in several incarnations already. This time it is to familiarize myself with Moose. As I know how I've implemented the graph in the past, I know that the differences/problems I encounter this time are most likely caused by Moose or my lack of understanding of Moose.

Take a look at the Graph modules. Chances are you're reinventing wheels;)

Update
Oops, missed that you already knew about Graph. It is definitely the place to look. Even if it does fully not solve your problem, you will have useful building blocks, i.e. data structures, common algorithms etc.