Here's what Paradroidz (
http://www.jpct.net/paradroidz) does to deal with this:
The calculations are grid based even if the game is actually presented in 3D. An entity is always located on a grid and has a global and a local target position on the grid. The target positions come from the path calculated by a modified A*-approach with taking only static obstacles into account. The global target position is the destination...it doesn't really matter in the calculation until it has been reached. The local target position is a position next to the actual position. If it's reachable, i.e. no other moving entity covers that position OR has it as a target position itself, the entity will move towards the midpoint of that position (in 3D) (with a slight chance to do something completely different to add a random element). If the target position is occupied (or most likely will be in the foreseeable future) by another entity, the next target position will be the exact opposite (compared to where the entity is now) of that position. That way, the entity tries to move out of a collision and resumes to travel its actual path only after it has reached this escape position. If the escape position is occupied too, it chooses a completely different global target.
Because the movement is done in 3D (at least when the entity is visible) and a grid is only a rough approximation of the actual position in 3D, a 3D ellipsoid collision detection acts as the last line of defense. Its outcome may change the grid position of the entity when it forces the entity to cross grid borders, but that doesn't matter. In the next iteration, it tries to reach its current local target from there.
Edit: That's how it basically works. There are some special cases that i had to cover, but that's really quite dependent on the game.
Edit2: Don't overcomplicate things. Often a simple "hack" can produce results that are "good enough", but again, this depends on the game.
