Turns out the solution was to declare Memoized as follows:

/**
 * Memoized function that exposes its cache.
 */
type Memoized<T extends Memoizable> = T & Memo<T>

/**
 * A memoized function exposes its cache as a read-only attribute.
 */
interface Memo<T extends Memoizable> {
    /**
     * The cache from which memoized items are retrieved.
     */
    readonly cache: Map<string, ReturnType<T>>;
}

Now the type hint looks like this:

View the full example on TS Playground