Suggested by Tyson Paul. To mitigate impact on organizations with large numbers of Subscriptions using "New" resolution state.
Pseudo Code (not tested)
$subs=Get-SCOMNotificationSubscription
foreach($sub in $subs)
{
{insert find magic here}
$sub.Configuration.Criteria = $newString
$sub.Update()
}