Fastest way and best way may not be the same in your case, based on the info you provide.
Since you have found that Migration of apps bring the slow performance back, I'm not sure I'd do any more migration, but would try re-installing the apps instead. This would create new preferences, eliminating an "bad, old preferences" that may have been the cause of the slow down.
Re-installing will take more time, and apps like those from Adobe that require key #s are going to be a pain, but the end result of a properly performing Mac is your goal.
The problem with Migration is that it can bring the problems with it, as you have seen.
The problem with re-installing is that you will never know which caused the problem. You won't be able to avoid creating the problem again. It may not have been anything you did, but a built-in glitch that is going to occur whenever a particular set of apps and actions are present.
Perhaps a faster way to solve the problem of what causes the slow down:
Make sure all 3rd party apps are in the Applications folder, or have aliases there, so all User accounts have access to them. Then log out of your account and into another account and test for performance problems. I have an account called "Test" (non-Admin) just for this purpose. This account will have its own preferences for those apps, different than yours.
Now, in that Test account, start using the apps and your Mac, watching for slow-downs.
Whatever you do to solve this, please come back and report it- what worked and what didn't. We all can learn something from it.
You can't get that dialog back, but you can inherit the backup manually via Terminal using the tmutil command. Do man tmutil
for more information.
Example:
$ sudo tmutil inheritbackup "/Volumes/Time Machine/Backups.backupdb/iMac"
For more information, see the blue box here: http://Pondini.org/TM/B6.html and you would do well to read the whole page before starting the process.
Best Answer
I finally got a solution for this in the Apple forums. Still not sure why it worked but, here's what was suggested:
I had to leave the machine overnight but this morning, Messages search works again.