From a real-world viewpoint: If you were headed from A to B and found a door D in your way that was locked, you'd realise you have to find key D. So if your AI is as unknowing as the typical human is, that would involve scouting for the key, which is a set of tiny pathfinding steps in and of itself. On the other hand you might want your AI to know, before even attempting a path, that there is a locked door on that route, and in that case it will probably also know where to find the key.
Either way, the issue is one of connectivity at two levels. At the "on-the-ground" level, you know you can always move safely within one undivided zone... undivided by locked doors, that is. This is where you can use your current A* pathfinding implementation freely. (In a simplistic example, you could see a zone as a single room. You can't get to any other room without unlocking a door. In reality, it could be an entire region of your dungeon.) This is the foundation of your entity movement, but it's a bit like walking around with your eyes downcast, instead of surveying the area around you first -- you're likely to walk into a lamppost. Or in this case, a locked door. So your ground-level maps which your A* runs on must restrict the player to movement only within the current zone.
Next, there is a higher level map, which is more topological than topographical in nature. It doesn't really care about the on-the-ground details of obstacles and so on, it only cares about the connectivity between zones. This topological map bears connections between even zones that currently have a locked door between them, since it shows the ideal connectivity of all zones in your dungeon. In it's edges -- each representing a door between zones -- it stores what key is yet needed, if any, to open that door, else it is considered open. So in searching this graph for shortest path, it should limit that found path to only routes that are already open, by checking the data in the edges as the search runs. Connectivity here does not imply openness, rather it implies potential openness.
When you want to move to a point that falls within a separate zone, you first search your higher level map to find a path. (A* or any other shortest path algorithm may be used at this level.) Once you find a path, that higher level map should also provide info on which door you need to use to get from your current zone to the other zone. Now, in the local zone, you can do ground-level AI to navigate to that door. Once the door has been reached, your character can pass through that door/portal. He is now in zone B. If this is the target zone, he can use ground level navigation to go to the key. If it isn't, then you need to repeat step one until you reach the target zone.
There is the possibility that a key being sought is itself behind a locked door... and that the key to that door is likewise... and so on ad nauseum. This is essentially a dependency resolution problem, and there are a few ways to tackle this, one of which is Petri Nets. See this excellent paper.
PS. If you are creating your dungeon procedurally, then as you do so, you can store information on dependency ordering, provided you already know the starting position of the player.