A little history on this problem before I share my experience. It may be of value to somebody.
The form notifications were firing inconsistently. I'd fill out the form and get notified. The agency that hired me wouldn't. Occasionally a customer "in the wild" would fill out the form and notifications would fire. Occasionally they wouldn't. There was no rhyme or reason. I couldn't find a pattern.
PROBLEM #1: INCONSISTENCY
I had the Sender Email address dynamically set to the submitter's email. This worked fine in all my setup and testing, except - as it turns out - in cases where the submitter was using a @gmail, @hotmail or @yahoo address. These would fail silently. This is probably due to the SMTP issues discussed here, but email isn't in my skill set so that's just a guess.
The inconsistency was due to human nature - I would default to my non-gmail/yahoo/hotmail address when filling out the form and it would work. Same deal with others. My client used a gmail address (and it failed).
When I changed the FROM and REPLY-TO all notifications were firing to all parties. Except the client.... Even when I changed the FROM/REPLY-TO to something innocuous like my email, the client's Office365 was still ignoring the notificaitons.
PROBLEM #2: SMTP
I know very little about email (more, now) so this took a while to sort out.
I did some Googling and found this was sort of a common thing, getting Office365 to play nice with notification emails from forms. SMTP always seemed to be the answer so I looped in the Office365 admin and got that info.
Entered it and hit the "Test Email" button. No dice. Errors.
While I Googled around looking for explanations and we added the web server's IP to a whitelist in Office 365.
Back in SMPT-land I was thrown by the labeling of the field System Email Address in the Craft settings and the instructions "The email address Craft will use when sending email." I took that to mean the address the System would send reports to which was set to my email address.
On a whim I tried the SMTP login email there as well and the test email worked (as @Ben Parizek wisely suggests).
I then changed the FROM/REPLY-TO to the Office365 address (which is also the TO address, by the way) and all is functioning smoothly.
I'll take the blame on that one, though I believe a clearer instruction line could help. Maybe something including "From"...
All is functioning now and everybody is happy. The client was wonderfully patient during this whole process so I count myself lucky in that regard.
A special shoutout to the Sprout support team who were looking into Problem #1 when it got sorted out. They were very helpful and responsive.