What are the best practices for notifying a merchant that a payment has been completed?

Email.

A digitally signed email (think: non-repudiation). Also maintain a set of transaction logs internally, again digitally signed, so that you can prove in a court of law (as and when required) that the logs were not tampered with.

Additional CYA: A complete log of your MTA (aka Mail Server) for all the emails delivered.