I remember a few years ago(2002) there was a multipartite virus that could be run natively on linux and windows. I don't know if a compiler could be specially craft an executable so that it could be read as both ELF and PE, so that the os would start executing at different entry points. Or a program that could merge two programs, one compiled using mingw, one compiled in native linux, to one program.
I don't know if such a program exists, or could it exist, and I'm know this could be implemented in Java or some scripting language, but that's not a native program.
Imagine the possibilities, I could deploy a program with linux and window (and perhaps os/x)libraries, and one main executable that could be run on any os. The cross-platform support would compensate the bigger size.