Last Changed did not update properly, how to fix?

Use any sql client and look at the states table.

You will see that these rows are updated on every restart of HA.

A while ago i had the same problem and created a python shell script.

It fetches the last few states from an entity and returns the last_changed value if the state realy changed.