Objectless A* Implementation

Objectless A* Implementation

My current pathfinder is a .NET 2.0 implementation of Eric Lippert's Path
Finding Using A* in C# 3.0 series. Eric's pathfinder is excellent (if you
haven't read his articles, do read them), but I wouldn't agree with the
assertion that in order to get a faster implementation of A* you'd have to
use C++.
Eric's algorithm creates an enormous amount of temporary objects each time
it is ran, even if the Node type is a struct; every piece of a Path is an
object, and a large percentage of insertions into his PriorityQueue class
results in a new Queue object.
In my application, I have to generate a large number of A* paths in
soft-realtime, but I'm allowed to give-up after the closed-list exceeds a
certain threshold. It should be possible for me to run A* without
allocating any new memory between calls. However, presently nothing is
reused, everything is reallocated again on the next call.
If I were coding an A* implementation in C++, one of my design goals would
be allowing the user to specify a starting capacity of the pathfinder and
reusing any memory allocated for the next time the pathfinder is ran
(whatever results the user wanted to keep, that user would be instructed
to make a copy). This is an extremely efficient approach, and I think it's
something C# can accomplish also.
This seems like it could be really tricky to write though, has it ever
been done before? Are there pitfalls that you'd think I'd run into with
trying to implement it?
The non-trivial problematic areas in Eric's algorithm are:
Path (an implementation of an immutable stack) - Forces the use of objects
(regardless of whether Node is a struct).
PriorityQueue - Most insertions will result in a new Queue object, and
when it doesn't, it could still result in the Queue doing an internal
resize.