The reason this is failing is that the episerver output cache uses cache item dependencies (depend on another cache key) which doesn't seen ti be supported for custom output cache providers.

Below is a workaround that makes takes the exception away (but probably doesn't invalidate properly). The solution overrides a method in PageBase. I don't know whether this is viable in this situations, but perhaps it can help you along. I'd be interested to learn what you end up with.

        protected override void SetCachePolicy()
        {
            string cacheVaryByCustom = EPiServer.Configuration.Settings.Instance.HttpCacheVaryByCustom;
            int cacheVaryByCustomLength = cacheVaryByCustom.Length;

            Response.Cache.SetVaryByCustom(cacheVaryByCustom);

            string[] cacheVaryByParams = EPiServer.Configuration.Settings.Instance.HttpCacheVaryByParams;
            foreach (string varyBy in cacheVaryByParams)
            {
                Response.Cache.VaryByParams[varyBy] = true;
            }

            Response.Cache.SetValidUntilExpires(true);
            // Cannot use cache item dependency when using OutputCacheProvider
            // Response.AddCacheItemDependency(DataFactoryCache.VersionKey);
            Response.Cache.AddValidationCallback(new HttpCacheValidateHandler(ValidateOutputCache), null);
            DateTime cacheExpiration = DateTime.Now + EPiServer.Configuration.Settings.Instance.HttpCacheExpiration;
            DateTime stopPublish = CurrentPage != null ? CurrentPage.StopPublish : DateTime.MaxValue;
            Response.Cache.SetExpires(cacheExpiration < stopPublish ? cacheExpiration : stopPublish);
            Response.Cache.SetCacheability(EPiServer.Configuration.Settings.Instance.HttpCacheability);
        }

        private static void ValidateOutputCache(HttpContext context, object data, ref HttpValidationStatus validationStatus)
        {
            if (!UseOutputCache(context))
            {
                validationStatus = HttpValidationStatus.IgnoreThisRequest;
            }
        }

        private static bool UseOutputCache(HttpContext context)
        {
            return !PrincipalInfo.CurrentPrincipal.Identity.IsAuthenticated && EPiServer.Configuration.Settings.Instance.HttpCacheExpiration != TimeSpan.Zero && String.Compare(context.Request.HttpMethod, "GET", true) == 0;
        }    

Thanks for the answer Christian.

I think we'll end up rolling our own cache provider, but it's still to be decided.