Customer claims he didn't get his cash at the ATM but his account ws debited. We submitted an adjustment with our processor and gave customer prov credit. We received audit tape from other institution showing the transaction as completed and the ATM wasn't over. Are we ok in taking the prov cr back now that we have the audit tape from the other institution?

If you haven't finalized the claim, then the investigation revealed the machine balanced and showed the funds dispensed. You could pay it to keep the customer, or deny it based on the facts.

You need to follow the correct procedures and ensure there are no NSFs as a result of the debit, etc...

We finalized the claim...taking the provisional credit back.
Now we want to give the customer the benefit of the doubt (should have done so in the first place) and credit his account back. What should we say in our letter to him?

Something like "We've reviewed your claim and have determined that our decision was incorrect. We are crediting your account in the amount of $X.XX [decide whether you want to include interest and fees; I recommend you do], which includes [describe how you arrived at that figure]."

I wouldn't go so far as to say it was incorrect. I'd put on my Marketing hat and say:

"Dear Bob,

Upon reviewing your claim for ATM dispensing error, we determined that because the machine balanced as it should have, your withdrawal was dispensed. But we have also looked at your account history with us. You have banked here since XXX and not had claims like this in teh past. Because of your record with us, we value your business and have decided that we will pay your claim. Enclosed is a check/deposit ticket in the amount of $XXX.

We look forward to being your bank for the future."