A maze sounds like a real killer case when it comes to pathfinding unless there's a specialized algorithm, one specially made for mazes. The built in A* implementation is in the RTS behavior, which I've used to great extend with a fairly complex finite state machine AI.
I haven't looked into any pathfinding plugins myself because the RTS behavior has always cut it for me. A* is widely used in the game industry for its versatility (as it's a general search function F.E.A.R. even used it for AI decision making as well as their pathfinding), I'd be surprised if its performance wouldn't suffice unless it's a very well-defined case that requires heavy optimization.
That being said there's many ways of implementing A* and I don't know what kind of approach Construct has. You can read on this on Wikipedia.