I'm a beginner at pathfinding, so take these thoughts with a grain of salt:
I am using A* on a classic grid, but taking all units into account would mean repathing all units when one unit moves. Units are usualy only immobile for a very brief time, so thats not happening.
How about you don't take units into account, doing the regular A* you are currently doing, and if an entity is blocked by another entity and they are within a small range of each other (i.e. "10 ft"), then, preserving your existing A*, run a smaller local A* only taking into account the nearest tiles (the tiles within 20ft) with a "goal" of getting back on the "real" path from the original A*. Take into account other units only in the smaller A*.
If the entity can't find a way around, then just let him walk through the other entity (perhaps having each entity visually step to the side to pass around each other).
To prevent both entities from trying to move around each other at the same time, have the first entity "tell" the second entity not to bother changing its path.
Your entity normal pathfinding is gameplay-related. But the entities moving around each other - is that just visual polish, or gameplay-critical? You could just have them walk through each other and "sidestep" (each automatically moves a half-tile to their left if another entity is also on the same tile).