The issue here is because the keys returned from GetKeysStartingWith() include the prefix so when you pass the prefixed keys to RemoveAll it’s adding another prefix resulting in trying to remove keys that don’t exist.
This existing behavior is the same in Redis & Memory Cache Client WithPrefix as seen in this gist.
As this issue is more likely to occur than using conflicting keys with the same prefix I’ve updated CacheClientWithPrefix to only add prefix to keys when it doesn’t already exist in this commit.
This change is available from v5.9 that’s now available on MyGet.