This paper will report results of various different metaheuristic search techniques applied to a complex student allocation problem. The problem has what might be considered a particularly difficult solution sapce when using the most natural definition of neighbourhood structure. The difficulty concerns the presence of many "plateaux" - large areas of solution space where all solutions have the same overall cost - bordered by discrete steps up or down. The challenge for the neighbourhood search mechanism is to avoid becoming "stuck" on a plateau by finding routes across these plateaux that will eventually lead to a step down, i.e. a reduction in overall cost.