I found this paper that might be interesting/useful to Ashley if you don't know it already.
Its written by a David Silver from The university of Alberta and called "Cooperative pathfinding", and seems to offer an alternative to A*, I don't really know a lot about it or whether it will be useful at all, to be honest, but it seems to cause some interest around the internet.
Anyway here it is, its only 14 pages.
http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/coop-path-AIWisdom.pdf
Here is an example of someone who have implemented it, and supplied the source code in Java as well.
http://www.jkilavuz.com/whca/