You might (for long distance pathfinding in a maze-like terrain) have to preprocess the map using some 'portal' technique to identify the chokepoints and build a A* network of those (and the 'room' area centers). The nodes (and edges?) would have an extra value of ClearRadius predetermined of what sized object can go through that nodes constrictions. Network edges would be prechecked paths between the node points on the map.
This all would be a coarse level navigation (and probably be a smaller network which will saves on A* processing). Out-of-sight navigation might not have to be perfect and the less-than-optimal 'paths' of a coarser network might not be significant.
Then you will still be doing the fine grid navigation while in-sight of the player or maneuvers more than just distance moving (where precise collision detection for moving nearer the obstacles is required - like moving near cover in combat).
Of course if you have dynamic obstacles then you will have to do separate processing to handle those.