String edit distance between strings x, y, with restrictions on 'intermediary' strings
I think your approach has merit, but you want to limit the amount of searches on $V$.

Model $V$ as a graph and connect all nodes whose strings have Hamming distance one. Then you connect $x$ and $y$ with all nodes at Hamming distance one, respectively.

Now the problem is just finding a shortest path from $x$ to $y$.