Cancellation by mail is always fine, no company can opt out of it in a legal way. You don't even need to get the address right, you can mail it to any subsidiary of the company - it is the companys responsibility to correctly route it internally. You can even directly address it to the CEO and at "persönlich" to it. My favorite.
In theory yes, in practice I had multiple disputes over contract termination and in 100% of those cases the counterparty with happy with the photo. And also compare it to any "phone calls" where you basically have nothing as a proof (dunno about your jurisdiction, but in Germany it is illegal to record phone calls without prior consent and also would require technical means to do so).
Also, if you ever worked in a large corporation, they have a lot of means to track incoming mail ("Posteingangsbuch") and for an enterprise to try to pretend not to have received a letter would require maldoing by a lot of employees (who usually are not commited to giving false statements in court for their employer).