You seem to be missing the point. You won't actually detect the full path (or even if it is possible to get there) until you actually went though all open/closed blocks. How many frames will it take - that depends on the number of blocks you check each frame vs number of all blocks. if you check 5 blocks each frame (for each unit) and you need to check 100 blocks to come up with full path, then it takes 100/5 = 20 frames to come up with full path - and that is OK.
1) Perform only several steps with each update while taking other enemies into account
This solution looks nice, however I cannot figure out how would I be able to detect if there is no path, since A* (at least the form I know) detects it from having an empty list of open nodes at the start of new loop.
All, that you really want to do, is just to give the player an illusion of instant pathfinding (even if it takes up to a second to come up with full path).
If your initial estimate was wrong, well that's OK. You never played an RTS where you give few units a command and they suddenly change their direction after a second ?
This is why it takes so long in those RTS games to finish the initial rotation towards the correct direction. While they are rotating, they're giving the player an illusion that they know where to go, even though, for a fact, they still don't.