Presumably, for paid invoices, the total amount due at the bottom of the invoice is $0.00 and your customers are missing that fact.

How about having a TEXT block that you insert on paid invoices so that it appears in the body of the invoice. Something to the effect:
Quote:

Thank you for your order! This invoice has been paid in full and this copy is for your records only. We appreciate your business!
_________________________
Andrew Bates