I solved it myself (that's a first and probably a last)!
I'm sure this isn't the best code but it works and I don't know enough PHP to clean it up.
I disabled all "No Results Behaviors" in the view settings. I'm using the hook_preprocess_views_view hook to count the number of results for each of my attachments. Only if all 4 === 0 will it print the correct empty message.
function MYTHEMENAME_preprocess_views_view(&$variables) {
$view = $variables['view'];
if ($view->name == 'search_results') {
$view1 = $view2 = $view3 = $view4 = $view;
if (is_object($view1) && is_object($view2) && is_object($view3) && is_object($view4)) {
$view1->setDisplay('page_1');
$view2->setDisplay('attachment_1');
$view3->setDisplay('attachment_2');
$view4->setDisplay('attachment_3');
$view1->execute();
$view2->execute();
$view3->execute();
$view4->execute();
if (count($view1->result) === 0 && count($view2->result) === 0 && count($view3->result === 0 && count($view4->result) === 0)) {
$variables['empty'] = "Sorry, but we couldn't find any results for your query. Try broadening your search terms.";
}
}
}
}