cryptdisks-early unlocks device as "unformatted" with UUID in fstab

You have the encrypted device referred with either a label or blkid in your fstab.
There is a race condition so that the thread/process waiting for the encrypted filesystem to become available will "catch" the availability event and device before the cryptsetup scripts have time to rename the block device from foo_unformatted to foo. Because the mounting thread is faster, it gets to mount (and lock) the decrypted device while it still has the temporary name.

This is obviously a bug in the startup scripts. A simple workaround would be to refer the block device by its path and not by blkid/label in /etc/fstab. If referred by path, the mounting scripts will wait until the device with path /dev/mapper/foo is available (which will happen only when the cryptsetup scripts get to rename the temporary device)

I use UUID= in fstab. UUIDs are persistent, what /dev/mapper/ paths are not. How about fixing the race condition?

I agree they should fix the race condition.
As about /dev/mapper paths being or not persistent,at least for this scenario they are persistent (as /etc/crypttab sets the exact name the device should eventually have in /dev/maper ("foo" in this case). For a desktop/laptop the workaround is good enough. Of course, I would preffer to have the bug corrected :)

Is it okay to run with the filesystem mounted as "_unformatted" or should I avoid UUID for this use case?

Also, I'm on 14.04. Haven't tried this on 16.04. I wonder if this is still an issue under the systemd regime.