I was having problems with the email notifications as my domain name is with a different provider to my website. I didn't really want to bring them both together as in my mind this creates risk for the business in that the web host retains all the control.
One request to admin - can we get a sticky that describes all the ways email notification might not be working - based on the issues identified so far in this forum and what can be done about it (e.g. godaddy issues/plugin conflicts, smtp setup etc)
Also - I got around my issue by setting up gravity to send email notification to an external email in GMAIL that then forwarded gravity form notifications back to my business email.