How did you reconcile your discovery in the previous question (that the UDF filesystem should be created on the whole disk, not a partition) with that Windows command ("format x: /fs:UDF")? In my attempts, Windows only gives drive letters to partitions.
As far as formatting for compatibility, I think the key is in the block size. Since most hard drives and USB flash sticks have a block size of 512 bytes, I've had the most compatibility when I create the FS that block size. I think format.com is using that block size, and mkudffs has a command switch for changing the block size. I could only get OS X and Windows to mount the filesystem when I used 512 byte blocks. Older versions of Linux assumed a block size of 2048, but you can always mount with "-o bs=512".
The whole disk vs partition issue still causes compatibility problems. Windows won't mount when I format the whole disk, and OS X doesn't look beyond the partition's type number when determining its filesystem, forcing me to mount it manually. Linux didn't care, as long as I gave it the appropriate device name (sda vs sda1).
In summary, the most compatible setup I've found is a singe partition of type 06(FAT16), formatted with UDF at block size 512. Works automatically on Windows, and a small bit of manual intervention on Linux and OS X.