I'm not sure they're actually using A*. In the following video, some cars are going directly right, although it isn't the shortest "bird-view" distance to their destination.

http://www.youtube.com/watch?v=l_ufAd79bOA

Edit: actually, they seem blocked by cars from the left lane. They'd go left otherwise!

Though I can't find any official sources to back it up, various internet citizens seem to claim they're using a D* Lite algorithm. I find it hard to believe. Either they're using some much cruder algorithm or they've implemented D* Lite horribly.

D* Lite Source https://twitter.com/MaxisGuillaume/status/311218564600315905

They should be using min-cut max-flow graph algorithms rather than dist based metrics.