Obviously Lannisters are deceitful and lacking emotional apathy. Is it possible that their claim that "A Lannister always pays his debts", false?
"A Lannister always pays his debts" is meant to appeal to the greedy, and to sway them to overlook the reputation of being deceitful that the Lannisters may have, when it comes to bribery and making deals. This is, after all, the house that sacked King's Landing, murdered King Aerys, murdered the entire houses Tarbeck and Reyne. The saying is meant to assure people that whatever else happens, you will get your money.
This is also demonstrated several times, for example when Jaime pays the Bolton men the money he promised them for returning to Harrenhal to fetch Brienne, or when Tyrion pays Mord the gaoler at the Eyrie all the gold he carried with him (but he kept the silver).
It is also a part of their deceitful nature that while they may promise gold, that does not mean you are safe, like the silent threats that Jaime and Tyrion think during these exchanges. Jaime thinks that Tywin might fill someone's pockets with gold as he hangs him, and Tyrion offers to take Mord into his service to be able to exact revenge later on.
Later on, Tyrion-gone-mad also extends the saying to include revenge, meaning that "A Lannister always pays his debts" means that Lannisters always exacts revenge.
Either way, this saying is just a way for GRRM to strengthen the impression of the untrustworthy Lannisters. Trust them at your peril.
Their real family words are: Hear me roar!
The answer by @TLP gives the correct interpretation of the words in that they are just that, words. They are meant to make people think if they side with the Lannisters they will become wealthy. The words are coined to them as a popular phrase though their true house words are "Hear Me Roar".
His father ignored the sally. "The honor of our House was at stake. I had no choice but to ride. No man sheds Lannister blood with impunity."
"Hear Me Roar," Tyrion said, grinning. The Lannister words. "Truth be told, none of my blood was actually shed, although it was a close thing once or twice. Morrec and Jyck were killed."
A Game of Thrones, Tyrion VII
However, to answer the actual question at hand there is at least one case where a Lannister doesn't pay their debt. In this case it is Tyrion who tries to send Shae away.
"I don't want to leave. You promised you'd move me into a manse again after the battle." Her cunt gave him a little squeeze, and he started to stiffen again inside her. "A Lannister always pays his debts, you said."
"Shae, gods be damned, stop that. Listen to me. You have to go away. The city's full of Tyrells just now, and I am closely watched. You don't understand the dangers."
A Storm of Swords, Tyrion II
It's important to note that "A Lannister always pays his debts," cuts both ways and that the non-monetary interpretation is very important on the flip side. When we talk about interpreting the phrase as a promise of revenge, you can start to see how it is also a promise that the Lannisters will be called to account for all their various evil deeds.
Here are two prime examples: Joffrey dies from poisoning; Tommen jumps from a window in the Red Keep. King Joffrey dies by the exact same method as the king immediately preceding him, King Robert Baratheon -- which was an assassination orchestrated by Cersei. Tommen dies in a way that is clearly reminiscent of what was perpetrated on Bran Stark: youngest Stark, Bran, was pushed from a window by Jaime; and youngest Lannister, Tommen, jumps from a window. To me, this is a clear demonstration that the Lannisters create karmic debts with their deeds, which they are forced to pay back with blood.
Do they "always" pay their debts? While these are just words, part of the Lannister legend, really, it seems that their reputation for paying monetary debts is well-earned, even though the receivers may not always like the manner in which the debt is paid -- which is part of the cruel beauty of this phrase. In the metaphysical sense, it is still TBD whether there is enough Lannister blood left to truly pay for all their most evil deeds. (E.g. what could possibly happen to the Lannisters to fully pay back the massacre of the explosion of the Sept of Baelor?)