Which version do you use? PersistenceUtil.loadAndStoreInDataContainer performs the cache store load & data container save under lock.

By 'in front of a custom data store' I though you're implementing CacheLoader/CacheWriter SPI (usually referred to as cache store). So you update the cache yourselves, using the Cache API? In that case you really have to implement some sort of tombstones, or do the locking yourselves. Note that tombstones are generally troublesome if you want to use eviction, as ATM there's no way to say 'ignore eviction on these entries'. But expiration works quite fine.

I had quite similar requirements for Hibernate ORM's second level cache, so you can check out the implementation in ORM 5.1 to see how this can be accomplished. For efficient operation, you'll probably need to write your own interceptors, though, you could try different approach with functional API (ORM implementation was written against Infinispan 7.2 which lacked this functional API).