I went for the IContentUrlCache approach. My scenario is that one product can belong to two different root (segment) categories and based on current segment context (selected by user), the product should have a unique URL.

I think you might get problems with invalidating cache. If there are multiple markets for one language, they will invalidate each other, leading to very few cache hits.

My implementation for IContentUrlCache was quite simple actually. I created an interceptor that looks like this (more information at the end about registering the interceptor):

public class CustomContentUrlCache : IContentUrlCache
{
    private readonly IContentUrlCache _contentUrlCache;
    private readonly ISiteSegmentContext _siteSegmentContext;

    public CustomContentUrlCache(
        IContentUrlCache contentUrlCache,
        ISiteSegmentContext siteSegmentContext)
    {
        _contentUrlCache = contentUrlCache;
        _siteSegmentContext = siteSegmentContext;
    }

    public string Get(ContentUrlCacheContext context)
    {
        var newContext = new ContentUrlCacheContextWrapper(context, _siteSegmentContext.GetCurrentSegment());

        return _contentUrlCache.Get(newContext);
    }

    public void Remove(ContentUrlCacheContext context) => _contentUrlCache.Remove(context);

    public void Insert(string url, ContentUrlCacheContext context)
    {
        var newContext = new ContentUrlCacheContextWrapper(context, _siteSegmentContext.GetCurrentSegment());

        _contentUrlCache.Insert(url, newContext);
    }
}

This is the ContentUrlCacheContextWrapper implementation:

public class ContentUrlCacheContextWrapper : ContentUrlCacheContext
{
    public ContentReference CurrentSegment { get; }

    public ContentUrlCacheContextWrapper(ContentUrlCacheContext context, ContentReference currentSegment)
        : base(context.ContentLink, context.Language, context.Host, context.VirtualPathArguments)
    {
        CurrentSegment = currentSegment;
    }
    
    public override int GetHashCode()
    {
        var hashCodeCombiner = new HashCode();
        hashCodeCombiner.Add(base.GetHashCode());
        hashCodeCombiner.Add(CurrentSegment);
        return hashCodeCombiner.ToHashCode();
    }
}

The HashCode class used above comes from the Nuget package Microsoft.Bcl.HashCode.

If you haven't registered an interceptor before, here is sample code for it:

[ModuleDependency(typeof(ServiceContainerInitialization))]
[InitializableModule]
public class InterceptorsInitialization : IConfigurableModule
{
    public void ConfigureContainer(ServiceConfigurationContext context)
    {
        AddInterceptors(context.Services);
    }

    private void AddInterceptors(IServiceConfigurationProvider services)
    {
        services.Intercept<IContentUrlCache>((locator, contentUrlCache) =>
        {
            var routingOptions = locator.GetInstance<RoutingOptions>();

            return routingOptions.UrlCacheEnabled()
                ? new CustomContentUrlCache(contentUrlCache, locator.GetInstance<ISiteSegmentContext>())
                : contentUrlCache;
        });
    }

    public void Initialize(InitializationEngine context)
    {
    }

    public void Uninitialize(InitializationEngine context)
    {
    }
}