So I found the error, and a fix would be to create a CustomVersioningDirectory extending VersioningDirectory and overriding Search(). The only problem is that I have to replace a lot of classes (VersioningDirectoryHandler, VirtualPathVersioningProvider, ++) because of a lot of internal constructors. I guess EPiServer don't want us to tamper with it? Has anyone successfully made customizations or extensions of EPiServers VPP-code? (can't find any examples, only custom VPPs written from the ground up)

The following hack fixed it:

/// <summary>
/// Custom versioningdirectory adding * when searching in EPiServer's filemanager
/// </summary>
public class CustomVersioningDirectory : EPiServer.Web.Hosting.VersioningDirectory
{
    public CustomVersioningDirectory(EPiServer.Web.Hosting.VirtualPathUnifiedProvider provider, string virtualPath, EPiServer.Web.Hosting.Versioning.VersioningDirectoryHandler dvdh, VersioningFileSystem fs, string customSummaryFullPath, bool bypassAccessCheck)
        : base(provider, virtualPath, dvdh, fs, customSummaryFullPath, bypassAccessCheck)
    {
    }

    public override UnifiedSearchHitCollection Search(UnifiedSearchQuery query)
    {
        if(!string.IsNullOrEmpty(query.FreeTextQuery) && (!query.FreeTextQuery.EndsWith("*")))
            query.FreeTextQuery += "*";

        if (!string.IsNullOrEmpty(query.FileNamePattern) && !query.FileNamePattern.EndsWith("*"))
            query.FileNamePattern += "*";

        return base.Search(query);
    }
}

public class CustomVirtualPathVersioningProvider : EPiServer.Web.Hosting.VirtualPathVersioningProvider 
{
    private readonly VersioningFileSystem _versionFileSystem2;
    private readonly VersioningDirectoryHandler _rootVersioningDirectoryHandler2;

    public CustomVirtualPathVersioningProvider(string name, NameValueCollection configParameters)
        : base(name, configParameters)
    {
        _rootVersioningDirectoryHandler2 = null;
        _versionFileSystem2 = null;

        Type type = base.GetType();
        var field = type.BaseType.GetField("_versionFileSystem", BindingFlags.NonPublic | BindingFlags.Instance);
        if (field != null)
            _versionFileSystem2 = (VersioningFileSystem) field.GetValue(this);

        var field2 = type.BaseType.GetField("_rootVersioningDirectoryHandler", BindingFlags.NonPublic | BindingFlags.Instance);
        if (field2 != null)
            _rootVersioningDirectoryHandler2 = (VersioningDirectoryHandler) field2.GetValue(this);
    }

    public override System.Web.Hosting.VirtualDirectory GetDirectory(string virtualPath)
    {
        string handledPath;
        if (!this.TryGetHandledAbsolutePath(virtualPath, out handledPath))
            return this.Previous.GetDirectory(virtualPath);

        var secretString = GetInternalVPPReadOnlyPageDir();

        if (object.ReferenceEquals((object) this, (object) VirtualPathHandler.PageFolderProvider) && string.Equals(secretString, handledPath, StringComparison.OrdinalIgnoreCase))
            return (VirtualDirectory) this.ReadOnlyPageDirectory;
            
        virtualPath = handledPath;
        List<string> directories;
            
        if (!this.TrySplitVirtualPath(virtualPath, out directories))
            return this.Previous.GetDirectory(virtualPath);
            
        VersioningDirectoryHandler handler = this.GetHandler2(directories, directories.Count);
        if (handler == null)
            return (VirtualDirectory) null;

        //replacing with our own CustomVersioningDirectory
        var customVersioningDirectory = new CustomVersioningDirectory(this, virtualPath, handler, _versionFileSystem2, ConfigFileSummaryFullPath, BypassAccessCheck);

        if (!customVersioningDirectory.QueryDistinctAccess(AccessLevel.Read))
            throw new UnauthorizedAccessException("You are not authorized to access " + virtualPath);

        if (!this.AcceptDirectoryRequest((UnifiedDirectory)customVersioningDirectory))
            return (VirtualDirectory) null;
            
        return (VirtualDirectory)customVersioningDirectory;
    }

    /// <summary>
    /// helper-method to get private string VirtualPathHandler.VirtualPathToReadOnlyPageDirectory
    /// </summary>
    /// <returns></returns>
    private string GetInternalVPPReadOnlyPageDir()
    {
        var myPageDirectoryRootVirtualPath = string.Empty;
        Type type = VirtualPathHandler.Instance.GetType();
        var field = type.GetField("_pageDirectoryRootVirtualPath", BindingFlags.NonPublic | BindingFlags.Static);
        if (field != null)
            myPageDirectoryRootVirtualPath = field.GetValue(VirtualPathHandler.Instance) as string;            

        return VirtualPathUtility.AppendTrailingSlash(myPageDirectoryRootVirtualPath + 0.ToString());            
    }

    private VersioningDirectoryHandler GetHandler2(List<string> pathStructure, int depth)
    {
        VersioningDirectoryHandler directoryHandler = this._rootVersioningDirectoryHandler2;
        for (int index = 0; index < depth; ++index)
        {
            if ((directoryHandler = (VersioningDirectoryHandler)directoryHandler.GetSubDirectory(pathStructure[index])) == null)
                return (VersioningDirectoryHandler)null;
        }
        return directoryHandler;
    }
}

http://world.episerver.com/modules/forum/pages/thread.aspx?id=25892