I've got a Word2016 32bit machine and haven't seen this behaviour (perhaps it is because I don't often delete styles unless I am doing large scale cleanups). Do you want to post a sample doc with the problematic style so I can have a look at what you mean?

__________________
Andrew Lockton
Chrysalis Design, Melbourne Australia