There is not enough info to tell anything for sure, but I had very similar experience once.
I tell you my story, it may give you some hints, where to find the problem.
My story was about simple problem to solve: there were two shipments which had to be done with the same vehicle and the delivery of the first had to be immediatly before the pick up of the second. I made the constraint and found that it had been violated in the solution. Then I learnt that with constraints, also the insertation and ruin strategy had to be rewritten to match the criteria.The reason was that even when insertaion ensured the constraint, ruin didn't honor it. I made the changes to the strategies, but then the solution had become sub optimal, because when the ruin removed only one of the activities, it were forced to put it back exactly where it were, literally freezing the initial solution.
The solution for the problem would have been to alter ruin to remove both jobs or none. (Instead of doing it, I redefined the meaning of job to handle the three activities as one. It is on an unofficial, yet unpublished branch.)
I'm not completely sure if your situation matches my case, but it may give you some lead. Stefan may give you better explanation, though.