A* on a 600x600 mesh is slow, especially if there is no valid path. in current cstrike bots we talk about A* on graphs with usually <4000-8000 nodes
I wrote a bit about my A* implementation on
http://www.lampel.net/johannes/joebo...XPDoc-beta.pdf
maybe that helps a bit