Objects Not Really Deleted?
You can delete an object's physics and physic related strips still remain in the Dopesheet.
Delete these and often quirky behavior returns to normal. 

Try purging orphaned data in the Outliner's menu. 
Select 'Orphaned Data' (think that's what it's called). That will list several items as a rule. Scroll the Outliner's header strip to the right until you see 'Purge'. Keep selecting this until all that's left is 'Brushes'