Enhancing the A* Search
There are plenty of ways to refine the A* search to give you the results you want in a game.
First, you might not need the A* algorithm in all situations. Many 3D engines can easily check if a line from one location to another hits any obstacles, so you can easily tell if a creature can move to its goal in a straight path (or perform any tactical maneuvers).
Another idea is to enhance a path by smoothing out the corners using a Bezier curve. This way, instead of making sharp turns, a creature gradually turns around a corner, presenting a more natural movement.
Finally, some larger worlds might be so big that doing an A* search in-between frames could cause a visible slow down. What you could do is create a low-priority "worker" thread that calculates the path (the thread might even sleep for a few milliseconds every few nodes). A creature could make the request to the worker to calculate a path, and later the worker would signal to the creature that the path was found. This could make it appear like the creature "thinks" for a second or two before making a move.