Are there any file formats that support Physique and are compatible with Unity? I really don't want to start over from scratch and have to use the Skin modifier...
Yes there are - FBX supports that. You need to get a Physique to skin conversion 3ds Max plugin. Not sure if it is still supported by the newest Max.