The fun one to play with would be A-star, but you'd have to find a suitable heuristic. One obvious candidate is that if you have target list that is X long and a current list that is Y long, then you need at least abs(Y - X) steps to get there (since each step either adds or removes a number). That's admissable and would probably speed up the search quite a bit compared to regular BFS, but you could probably do a lot better. I'm thinking a heuristic based on the number of inversions or something.
I would suspect if you found a really good heuristic for A-star, that's about as good as you're going to get. Though maybe there's something more clever I'm not spotting.