The question is very hard to answer. We first have to settle on what "possible" means, and second we have to define feeding etc. in a sufficiently theory-independent way. On the first point, it could mean "does we know of an example, or is it reasonable to think that we could find it in language", but it also could mean "does the theory have a mechanism for describing it". On the second point, since feeding etc are constructs of ordered-rule theories, what does it mean for rules to be in a counterbleeding order if you don't have order? To simplify matters, I will assume that you are asking about theories with conventionally ordered rules though not necessarily SPE theory (still, not KSN theory).
Under the premise that the language has two separate progressive and regressive cluster-simplification rules, such that (a) C→Ø/C_ and (b) C→Ø/_C where there are no other conditions on "C", and where both rules are obligatory, for any input string /...VblγsnqV.../ where a>b, the input maps to ...VbV... (in standard SPE theory, and in any theory with rule iteration). If there are no other rules in the grammar, (b) can never apply and (b) cannot be learned. However, (b) could apply if there is a third rule (c) which creates new consonant clusters, for example high vowel syncope. Note that given (a), there will always remain one consonant, and you cannot remove all consonants by (a).
If (a) and (b) are optional, the answer is different. /...VblγsnqV.../ can map to numerous strings, where the output begins with b and selects any of the subsequent consonants: for example ...VbsnqV... or ...VbγnV... In that case, (b) becomes potentially applicable and learnable. If the subsequent rule (b) is obligatory, ...VbγnV... maps to ...Vn... and ...VbsnqV... maps to ...VqV... And if (b) is optional, ...VbγnV... maps to
...VbγnV..., ...VγnV..., ...VbnV... or ...VnV...
Again, you can never delete the last consonant, but you can end up with any subset of the input consonants in the output.
Now the question is whether the concept "bleeding" applies to the optional rule scenario. Conventionally, (a) bleeds (b) if some string α undergoes (a) and results in β, and β does not satisfy the structural description of (b) but α does. In the present rule pair, (a) bleeds (b) because α = ...VblγsnqV..., β = ...VbV..., α satisfies the SD of (b) and β does not. That is, by taking away some consonants, application of (a) reduces the number of consonants that (b) can apply to.
Counterbleeding is conventionally defined counterfactually, that is, if (b) were to precede (a) the order would be bleeding, but in fact (a) precedes (b). Now we ask if (b) hypothetically preceding (a) is bleeding – it is. If (b) were to precede (a) then α would be ...VblγsnqV..., its output β could be ...VnV..., and rule (a) would not apply at all to that – all of the triggering consonants would have been removed by prior application of (b). Thus (a) and (b) are in a mutual bleeding-counterbleeding order (from which we could conclude that they are also in a mutually bleeding order and a mutually counterbleeding order).
SPE theory requires that the input to (a) be scanned for all substrings satisfying the SD of (a) and applying those changes simultaneously; and then you move on to rule (b). So my computation above does not depend on simultaneous versus iterative theory. I conclude that SPE theory does allow what would be called mutual counterfeeding, under certain circumstances, thus "mutual counterfeeding" is theoretically possible, but complete deletion is not. (SPE does not embrace Kiparsky's feeding etc. functional terminology).
Now moving to the very first question, is there any theory where you can delete all consonants in an input string? If (a) and (b) are separate rules, you will always have at least a single consonant in the output (the case we have just considered). But if (a) and (b) are the same rule e.g. the rule is "C→Ø/C" using Bach's notation – which is not part of the SPE system – and if the SPE simultaneous application convention is followed, you will get complete deletion of the consonant string when the rule is obligatory. That is, the rule says "delete a consonant just in case it is adjacent to a consonant", and in any cluster of consonants, every consonant is adjacent to some consonant (so will undergo the rule). But a single intervocalic consonant will not be deleted (it is not adjacent to a consonant). However, it is not clear whether this constitutes "mutual counterbleeding", which is not a technical concept of the theory of ordering. And it is clear that this scenario contravenes your assumption that the two rules are indeed independent rules.
As for the "does it exist" question, there is no known case where C deleting adjacent to C results in complete erasure of the Cs in an input string. This can happen in case of C deletion adjacent to V so in principle cluster simplification and intervocalic elision could result in total C-deletion, and I would say that it is "possible" (dunno if I can think of an actual example); but that's a different scenario and is feeding, not bleeding.
There is also ample discussion in the literature showing that the simultaneous application theory is wrong, and that Howard's directional theory is correct (except I think he erred in including a possibility for simultaneous application, and agree with Jensen & Stong-Jensen that unpredictable directionality is a superior alternative).
