simple thought i'm sure has been thought of before:
Would it help to simply reduce the scheduled proc to only run every 5 minutes - or is it the actual bulk of notifications rather than just the querying that is expensive?
If it would help, i think we can all wait a few minutes to be emailed new posts.