There is no way to sort data by the date it was modified, so there's no direct way to get comments that have been most recently deleted.
About the only option is to occasionally page through all the deleted comments on the site (by only using the "include=deleted" parameter) and update any comments that have changed states the last time they were added to your database.