The problem is not in the second example, but in the first, and in the algorithm not being right. You fell victim to the simplicity of your test example, since 3 elements is not enough for testing permutations. Here is a more representative example:
list1 = DeleteDuplicates@RandomInteger[15, 10]
(* {1, 3, 8, 7, 14, 11, 13} *)
list2 = RandomSample[list1]
{8, 3, 11, 13, 1, 14, 7}
Creating the rules:
list1rules = Thread[list1 -> Range[Length[list1]]]
listdispatch = Dispatch[list1rules]
Now the key point: you need not just to apply the rules, which simply give you the positions of elements of list2 in list1, but you need the Ordering of those positions:
list2[[Ordering[list2 /. listdispatch]]]
(* {1, 3, 8, 7, 14, 11, 13} *)
since at some point, some real sorting should take place. Have a look also here and here, where I gave detailed discussions of very similar ideas. I also once wrote a package called UnsortedOperations, which has a collection of functions for doing similar kind of manipulations. The package lives here, and comes with a notebook containing examples of use for all functions in it.