Correct me if I am wrong (I am not a C++ programmer), but I don't think you can use a priority queue because you need to update the values.
Sure you can. The STL heap functions don't provide an update function, but you don't exactly need one in the context of A* if you keep enough extra state. A properly written heap update performs in O(log n) time, but the only way to perform an update using the STL provided functions is to modify the contents directly yourself and then call make_heap() which runs in O(n) time. This is not desirable. However, you don't need to do a full heap rebuild; as long as you keep flags to know when a node is opened or closed, you can simply keep throwing on the updated node cost values into your heap and every time you pop off the heap you should check if the node you retrieved is open or not. If it isn't open, just skip it!
This is how I've implemented my A* function. You may be concerned that you'll have multiple instances of a node in the heap with different costs, but this doesn't actually affect the correctness of the algorithm as long as you have a flag (or some other structure) to determine if the node is in the open list or not. The heap serves only to keep track of the next min cost node to explore, not to actually tell you if a node is open or not. And due to the relaxation process of edges inherent in shortest path algorithms, you will always be popping off the most current cost estimates to a node if you have multiple copies.
Using a good structure to retrieve the min cost node is critical to good performance in cases where you have a large map to path through, but possibly just as important is the initialization time. I haven't looked thoroughly at your code but I also suspect your graph initialization can be a bottleneck. You should profile or instrument your code so you know exactly which parts take the most time. If your main loop takes up a lot of time, chances are you need a faster structure to retrieve your min cost nodes. Currently, I'm inclined to believe that most of your performance is dependent the open list data structure, simply because you stated earlier that the performance depends heavily on the length of the path.