For what it's worth, I noticed that the "+omnifocus" works with some hosts and not others. If you haven't yet tried a gmail account with it, definitely do. I send all my OF emails to
myemail+omnifocus@gmail.com and it works like magic. Of course, the email address I put in the Allowed From addresses in the OF preferences is still just
myemail@gmail.com. Not sure if this is something you tried already or not, but would be great to hear if it helps at all. Good luck! - Nathan