Woot!
I figured it out, calling DataCache.Remove(key) will attempt to remove the item from the default region. While, not clearly shown above (_cache is a thin wrapper around DataCache), our Put/Get calls include a region name, but our Remove did not. I added the Region and the Remove worked properly.