That's kind of a strange reason to mark something as spam. The same thing happens even with huge sites like Twitter/Facebook, they send out emails with subjects like "you have a new follower" and must send out millions of these a day.
You may be able to get around this by making the subjects more unique. Most of the emails sent have extra parameters that can be added to the language files, though it seems these are not documented well.
Example: in the file qa-include/lang/qa-lang-emails.php, you can edit the lines with 'c_commented_subject' and 'q_answered_subject' to these:
'c_commented_subject' => 'Your ^site_title comment has been added to by ^c_handle',
'q_answered_subject' => 'Your ^site_title question was answered by ^a_handle',
So there will be much less duplication.
As for external mail services, yes you may find these work better. Honestly I've had nothing but problems with email provided by web hosts, always way too unreliable in my experience. Mailgun or Sparkpost are great alternatives.
