History store key order checks are not validated frequently until the search ends in the history store always. To ensure the history store is in the proper order for every datastore key, verify the history store order whenever the datastore key order is getting verified.