Yep compound index on the two fields filtered on.

I have A LOT of items relative to other folks so I'm probably pretty sensitive to these slow downs, but with the way the notification query is structured - every item driven query needs to do this mute anti join ... so one option is to just rewrite the notifications query to not need to do that but it's sensitive to changes because all columns need to match.

I'll take a look a the query analyzer. It might be choosing some obviously wrong query plan.