I really doubt SPF is going to help you since the message you're getting seems to indicate that they are responding to spam complaints. This indicates people have been marking emails from your server as spam. That would override any SPF record.
Google is notorious for not setting up any sort of feedback loop (https://en.wikipedia.org/wiki/Feedback_loop_%28email%29) so there is no way to see what sort of emails you are sending that people are marking as spam -- but their notoriety in this regard may only extend to me.
That said, make sure that the emails you are sending out contain clear instructions on how to disable any email.
Assuming the emails that caused this Google block originate from MediaWiki, it would be best if you could modify the emails to put something at the top to let people know they are getting this because they signed up for email notices on your wiki and how they can disable them. (Unfortunately I don't know how you could do that since I haven't looked into that yet.)
But do read http://www.google.com/mail/help/bulk_mail.html and take the precautions it mentions. SPF is one, DKIM is another, but a clear way to disable email is a third.
Finally, verify that the security of your system hasn't been compromised and no one is using it to spam people.