It started out completely broken, storing waypoints in Core Data and was taking upwards of four minutes to calculate a path. Switching to prefetching Core Data paths brought it down to about 90 seconds, but that's as far as it could go with so many Core Data faults firing.
What made it really fly was the change the underlying data to direct bitmap access on maps prepared from the source maps (shopping centre levels actually) and applying simple filters to generate monochrome maps where one color was walkable and another not. Then source and destination locations were obtained through the original Core Data coordinates and a quick search algorithm found the closest walkable point to both. The A* calculation took perhaps a second or two.
Not content with that we went further and drew more complicated maps with what amounted to train tracks, a network of walkable paths one pixel wide connecting every store to every store to narrow down the solution space. The result was instant A* pathfinding and it was a very neat feature in the app.
You can definitely do A* in Objective C - just get to know Instruments inside out and keep tuning. On a 5S I expect you could get away with a lot of inefficiency.
I think I basically tried almost every A* trick available (rectangular symmetry reduction, HPA*, points of visibility, jump point search, etc) but ultimately I couldn't make it run fast enough on iOS for our max level size which was about 100x100. It also couldn't be multi-threaded because it needed to work with online code (synchronous tick engine)...
What ended up happening was I found a full C implementation of Jump Point Search, and it was incredibly fast! I had already moved several parts of my code to C in order to speed it up, but I guess using a higher level language like Objective-C is just way too slow to have instantaneous path-finding on a 100x100 grid. I think this was the code I found https://github.com/Bio2hazard/cJumpPointSearch