I guess this really is a MADDE bug. I've created a debian source package with "mad dpkg-buildpackage -sa -S" and uploaded it to the autobuilder.
The package created by the autobuilder (containing the postrm script) installed fine - the same package created directly by "mad buildpackage" failed to install.

I've filed a bug about this.