In an ordinary view if there is a relationship it must be checked "required" in order for the empty text to be displayed. Using the Node Relationships module, empty text is not displayed if there is no row output, and no way to "require" the back reference relationship. I'm using the unformatted style and a custom row output views-view-fields.tpl.php and explicitly displaying fields, but that shouldn't matter since $empty is handled by views-view--page.tpl.php.