I visit frequently enough that I don't really need notifications, as true for the most of us that generate the notifications.
IF this were my forum facing the same issues of mail being blocked, I would do the following:
Queue up all notifications. Within the next 24 hours (or other period of time), if the subject topic of the notification gets visited by the user intended to receive the notification, then the notification is not required, and thus remove it from the queue. Any queued notifications not already seen can then be sent once they've been queued the long enough.
You could probably eliminate 90% of your outbound notifications that way.