Strictly speaking, no, mutual authentication does not protect against POODLE. Some details may matter, though.
The core of the POODLE attack is that there is a way, with SSL 3.0, to alter some records so that the receiving end will not notice the substitution with probability 1/256. With this protocol misfeature, attackers can "try" decryption guesses on a single byte of encrypted data, and will learn that byte with probability 1/256. On failure, though, the receiving end duly notices the problem, and the connection is broken. The important point here is that none of this is impacted in any way by the handshake details; certificate-based client authentication does not make that protocol issue disappear.
The classic, Web-based description of POODLE then applies that issue in a Web context, i.e.:
- The target is an HTTP cookie.
- The attacker can not only trigger the requests, but also traps any error, thus broken connections don't show up on the unwary victim's screen.
In that context, POODLE recovers the target cookie with an average of 128 connections per guessed byte (that number can be somewhat lowered by assuming that cookie bytes are printable ASCII characters).
In your case, the client application is probably not a Web browser, and, as such, it may be difficult for attackers to trigger repeated connections. Moreover, if you do mutual authentication with certificates then you might not have big fat session cookies, thus removing a juicy target. Nevertheless, attackers can still try their luck and guess some bytes, if they accept to break most connections on which they attempt a guess. Whether attackers can pull that off discreetly really depends on how the application behaves when connections get broken. In particular, if HTTP "keep-alive" is performed (as is customary for SOAP-over-HTTP-over-SSL), then the client expects some requests to fail (because the server lost patience and closed the connection) and to restart them silently, so chances are that attackers can make their guesses silently.
It shall be noted that POODLE is about a confidentiality breach, not an integrity breach. If you use SSL only so that data gets authenticated, but without sending anything actually secret through the SSL tunnel, then POODLE ceases to be a concern.
Summary: what provides mitigation for POODLE is not the client certificate; what may provide mitigation is that the client is not a Web browser. However, the protocol vulnerability is still there and may still be exploitable, depending on the details of your application protocol.
You should really think about updating these client applications. By maintaining SSL 3.0 active, you are looking for trouble.