Transient storage location? database/xcache/w3Total Cache?

In general you don’t work with storage in the case of transients. You work with Transients API which makes use of either database or Object Cache.

Object Cache implementations are arbitrary, it can make use of any back end out there anyone bothers to make work.

So effectively there is no way to bulk delete transients since there is no bulk delete in underlying Object Cache (some back ends just won’t be able to perform such operation).

For a public solution you would have to engineer your caching logic in a way that functions within these constraints.

One of the common techniques is including some sort of identifier in transient keys, so that changing identifier effectively makes “old” set inaccessible. Take note of key length limitations though.