Please attach the actual execution plan (not the estimated) as sqlplan files. Jpegs won't help much here...

Also, please post table and index definition of all tables involved and the actual query (since it might not be shown completely in the sqlplan).

As a side note: I don't think this question has anything to do with Notification Services. Why did you use this forum then to post your question? But there's no reason to re-post it. Just make sure to pick the correct forum with your next question (assuming there'll be one...)