On my server when I try to sort a chest with items that are enchanted or even mob eggs they get sorted but then move back to presorted state. When I remove them the chest gets sorted properly. I have No Cheat Plus installed on it but disabled the features that were meant to stop sorting from working.

People keep reporting these issues, they seem to be related to a plugin but I have never been able to make it happen myself.

I generally don't explicitly support Bukkit however, the general solution to these issues is to use something like MCPC+ that allows to load mods on the server and install InvTweaks -- that lets it bypass any attempt by plugins to mess with the sorting functions.

Wouldn't it be possible though to add a delay to the script by a few ticks? You could add it in with the SMP help option.