You could try out Scribu’s plugin, i believe this addresses the very problem you’re describing which has been reported on Trac a handful of times(but closed/deleted).
Category Checklist Tree by scribu
http://wordpress.org/extend/plugins/category-checklist-tree/
Related tickets:
Hope that helps.. 🙂