Hi guys, some really cool replies I was surprised to see so many :)
So just for clarity, this will be a top down map, an isometric world like Habbo hotel. The A* I've nicked from my rather unsuccessful (and of questionable taste, please don't judge), London Riots game. The system is A* and calculates neighbors by casting a ray between each node. I've modified it with ease to be equal square tiles instead and it worked a treat.
I haven't looked into putting in multiple "levels" yet, but I thought I'd be cheeky and get you guys' opinion on it before I began. The main problem is the heuristic. If I simply add 1 cost if the goal is on another level, then the path is going to go underneath the tile, then realize the stairs are miles away and things will get very slow very quickly.
I was going to counter this by splitting into 2 paths. So if I'm on level 1 and the goal is on level 2 then first I will find a path to some stairs, then from there a path to the goal. This leaves the following possibilities unsolved though:
1) What if the nearest stairs don't access an area where the goal is (but some other stairs do)
2) What if the goal is on the same floor, but the shortest path involves going upstairs then back down again.
I will illustrate all of this in a crudely drawn diagram drawn in MSPaint :)
I think I'm going to solve this mostly via level design. Don't design anything that will have the problems that come with my "stairs first" approach. I don't think it would be that much of a restriction for what I have planned for this system.
Also RE: the fellow who said we should all post what we're working on; I've been on an MMO for the best part of 9 months now and it's finally starting to shape up :)