Why is my algorithm version so slow with this input?
I've found the conceptual problem.
In a BFS kind of search, when optimization is needed because the length of the queue grows at critical speed, you have to take track of the visited items.

The goal is to avoid adding another item to the queue when it is already present a better item there.

Just some code, only to clarify the concept.

In my case I've added a visited map

let mutable visited = Map.empty&lt;char,((char list) * int) list&gt;


and I'm enqueuing only better items:

if visited.ContainsKey(solutionNext.tree.area) 
    &amp;&amp; (visited.[solutionNext.tree.area] 
        |&gt; List.exists (
            fun (keys, distance) -&gt; 
            distance &lt;= solutionNext.tree.distance
            &amp;&amp; solutionNext.keys |&gt; List.forall(fun k -&gt; keys |&gt; List.contains k)
        ))
then () 
else 
    solution_queue &lt;- enqueue solution_queue solutionNext
    let previous = if visited.ContainsKey(solutionNext.tree.area) then visited.[solutionNext.tree.area] else []
    visited &lt;- Map.add solutionNext.tree.area ((solutionNext.keys, solutionNext.tree.distance) :: previous)  visited


and skipping the worst ones 

while (MyQueue.length solution_queue &gt; 0) do
    let solution = dequeue &amp;solution_queue
    if visited.ContainsKey(solution.tree.area) 
        &amp;&amp; (visited.[solution.tree.area] 
            |&gt; List.exists (
                fun (keys, distance) -&gt; 
                distance &lt; solution.tree.distance
                &amp;&amp; solution.keys |&gt; List.forall(fun k -&gt; keys |&gt; List.contains k)
            ))
    then () else


Cost function

From a theoretical viewpoint, BFS can guarantee that the ﬁrst solution returned will be as short as possible, only if we can assume that every move has got a cost of 1. You could reduce the above examples to that, but the best fit remains a graph where the cost function is represeted by edges of different length.
With real cost functions finding the shortest path becomes more involved: this is exactly the case here. Especially because you have to optimize also the Space complexity (see previous paragraph), avoiding the worst-case time complexity of $O(b^d)$, with $b$ being the branching factor and $d$ the depth of the ﬁrst solution. You have described a scenario where $d$ is well known at start (the number of the keys in the maze) while the edge case you mention is obtained by a bigger $b$ (number of crossings of the maze)