The Answer™: Go get access to an Insect Shaman.

P.S. Ares apparently has done this (Threats 2).

Aren't Queens free spirits to start with? Just not free to roam the meat-plane?

EDIT: Well not "free" in the normal sense. But something very different happens when a Queen is banished (not just destroyed) back to the Insect Plane because it's a sucking noise that rips the awakened status clean from the Insect Shaman.

I checked out that thread before posting. That was more to do with the Shaman than the Queen. My main question with that post- How does the powerless Shaman get tot he Insect Spirit Metaplane to get the True Name of the queen?

In Magic in the Shadows in the Threats section about Insect Spirits. It says that only an Insect Shaman can visit such an alien Metaplane.

Astral Gateway, perhaps.

The section on them says that they have Spirit energy LIKE free spirits but that they only become Free once the Shaman is killed, or they break away from him (That is when they get more Free Spirit Powers and that they ALWAYS become Free when the Shaman dies). Non Queens can become Free, usually Good Merges, but it's not common.

See here.
Relevant sections scattered throughout.

Definitely make for an interesting meeting, since it is usually spirits who have this power. He'd better hope he doesn't run into the Place of Magic though (Though since it uses Skills it may not require him to actually have magical power).

"So you want to go where with the what now?"
"Hush burny boy, you got your Karma now make with the gateway!"

I think the prime source of Insect Shamans would be those that haven't brought their Queen through yet.

But that thread does discuss the possibility of the [vaguely defined] Aleph Society allowing them to regain some of their powers, or perhaps even another Queen doing so. This is an area of the unknown though because the Aleph Society is a plot end that has not yet been developed fully to explain exactly WTF is going and the implications of it on magical theory.

This bit caught my Eye

So for an Insect Shaman who has lost his Queen he needs to find an Insect Spirit with Astral Gateway.

"No honestly, it's not YOUR True name I'll be after" <fingers crossed behind back>

"My words are clear, but my meaning is obscure." - Noboru Takeshita

Just to be clear about where i'm going with this. This is not explicit in canon, but could be used to explain from reasonably within the confines of given canon why Queens don't appear to be just popping back in a month after their hive has been wiped:

Free insect spirits may have a life cycle that is different that other known free spirits, and a mobility to the meat-plane that is somewhat closer to that of the Horrors. When a free Queen insect spirit is disrupted and returns to their metaplane they do not go through the regular 1 month recovering processes of a normal free spirit to reestablish the path back. Instead they only recover a partial link, one that allows them to contact and communicate with a chosen awakened mage and become their "Totem". This shaman is needed to rebuild the "bridge" back for the free spirit to return.