Phil was kind enough to point out a link on the forums about A* and I also did some extra research, and I realized that obtaining the fastest A* algorithm is a very complicated task that depends on your exact needs. While the core of the algorithm is always the same, the small implementation details and data structures that are used count a lot. So I would have to rewrite everything form scratch and I don't want to do that right now, since my A* optimization was just so that I could fix the issues I talked about last time.
But I did do one more round of optimizations: I optimized the central node container. The recommendation is to use a priority queue but I do not think there is a name for the thing I am using. Anyway, I won't bore you with all the numbers. Suffice to say, that in release mode, with 700x700 maps, the algorithm finds a path in 45-50 ms with any kind of map: empty, maze or just random. Nice improvement. I'll leave it at that. At normal map sizes, it takes at most 10 ms and the average time over the usual distances is 3-4 ms.
This is when I realized that there is a huge bug in my algorithm that has been there from the start. I tried to fix it, but the fixed A* is about 8 times as slow as the broken one. My algorithm shouldn't even work. After some testing and experiments, I think my algorithm degrades to a very quirky version of Dijkstra's algorithm. This is probably why the performance degraded so much when the explorable region was big with my less then optimal container implementation.
I really should prove my conjuncture that my A* degrades to a Dijkstra's, but with the current performance I won't bother with it now. I'll leave it to when I do not have anything else to do.