In theory we could sue for our money, but the imbalance of power between an enormous multinational company and our small agency makes that utterly nonviable.

Have you even talked to a lawyer? You had clear contract terms, you delivered, they are in breach. That's the easiest case a lawyer has ever seen.

The real question is if it's worth suing, giving the lawyers a cut and pissing off the client, vs hoping they pay eventually.

There are statutes of limitations though, check those out. If you wait too long you might be totally out of luck.