Here's what fixed our problem (Moodle 2.7)
In the config.php there is a line of code:
$CFG->noemailever that was set to true. Once we commented this line of code out (or set the variable to true) we started receiving the emails.
This was after we did everything to ensure our email settings and cron were working properly.