EntityFieldQuery with pager and db_or using addTag
I found the answer to this issue.

Apparently the THEME_query_search_alter hook was triggered twice (also saw this happen when altering the standard Drupal user search query) and the new table was therefore joined into the final database query twice.

So when it tried to find results in the same table two times it kinda broke the search results, and returned these many many results instead of just a few.

The fix was then to check if the new table was already joined into the query, and this is how I did it (only changed the THEME_query_search_alter hook):

function hedeselskabet_query_search_alter(QueryAlterableInterface $query) {
    $keywords = $query-&gt;getMetaData('keywords');
    $words = "%" . $keywords . "%";

    if (!array_key_exists('n', $query-&gt;getTables())) {
        $or = db_or()-&gt;condition('title', $words, 'LIKE');
        $query-&gt;leftJoin('field_data_body', 'n', 'node.nid = n.entity_id');
        $or-&gt;condition('n.body_value', $words, 'LIKE');
        $query-&gt;condition($or);
    }
}


And now everything works. :)