How should I choose the neighborhood structure for simulated annealing for my problem?
Simulated annealing can cope with neighborhood structures where you have to walk quite a bit to reach a distant point. Of course, the minimum distance between two points in the state space should at most be polynomial in the problem size, but any reasonable optimization heuristics will also require this restriction. The 5000 moves are completely reasonable for simulated annealing, especially since this is linear in $m$.

Don't implement any moves which would be very expensive to evaluate. The strength of simulated annealing is that it can work with moves which are cheap to evaluate, and hence evaluate a large number of candidate solutions. But if your state space is large, then you should also let simulated annealing evaluate a large number of candidate solutions. So your cool down schedule becomes important in this case. I could go into more detail here, but the question was about the neighborhood structure only, and the answer to this question is that your neighborhood structure is basically OK, and you should not use a neighborhood structure which would lead to expensive recomputations.