I solved this by copying the method GetDocumentsWithTags from umbraco.cms.businesslogic.Tags.Tag and change the select query as follows:

public static IEnumerable GetDocumentsWithTags(string tags)
        {

            var docs = new List();
            string sql = @"SELECT DISTINCT cmsTagRelationShip.nodeid from cmsTagRelationShip
                            INNER JOIN cmsTags ON cmsTagRelationShip.tagid = cmsTags.id 
                            INNER JOIN umbracoNode ON cmsTagRelationShip.nodeId = umbracoNode.id
                            INNER JOIN cmsDocument ON cmsTagRelationShip.nodeId = cmsDocument.nodeID                        
                            WHERE (cmsTags.tag IN ({0})) AND nodeObjectType=@nodeType
                            AND cmsDocument.published = 1 AND (cmsDocument.expireDate > @currentDate OR cmsDocument.expireDate is null)";

            using (IRecordsReader rr = SqlHelper.ExecuteReader(string.Format(sql, GetSqlStringArray(tags)),
                SqlHelper.CreateParameter("@nodeType", Document._objectType), SqlHelper.CreateParameter("@currentDate", DateTime.Now)))
            {
                while (rr.Read())
                {
                    Document cnode = new Document(rr.GetInt("nodeid"));

                    if (cnode != null && cnode.Published)
                        docs.Add(cnode);
                }
            }

            return docs;
        }

This is definitely one of the strengths of open source projects :)

Thanks a lot for the pointers Tim!