The lack of 16-bit support in the CPU makes things a bit more complicated, but still not impossible. QEMU user mode achieves this for example.
You are just too funny, do you think you can not use wine (which is mainly 32 bit) to run a 16 bit win app on Linux (does not matter if 32 or 64 bit)? Basically you need just a little hack (if not already done by the wine package):
sudo sysctl -w vm.mmap_min_addr=0
So Linux is even more compatible with older win executeables than W7 64bit, who expected that ;)
The greatest headaches were causes 32 bit applications which were still using 16 bit installers. Microsoft then wrote 32 bit drop-in replacements for some of the more popular installers.
I think if you use 64 bit wine, you can't even run 32 bit programs. At least it used to be like this until recently.
Most distros ship 32 bit wine for this reason even on 64 bit installs.
Microsoft has one of the worst engineering strategies of any software companies. Instead of fixing code or rewriting it to be better they simply add more. This additive approach creates a nearly grotesque mangled mess of an OS that is nearly gigabytes in size just for core files. People simply write endless amounts of garbage code just to look better because of the competitive nature of that business. From the User perspective everything works because layers and layers of code have been written to get it to work that way at all costs. However when something breaks it's usually just turned off and something else is written to replace it. Nothing is really "fixed" with Windows. Look at security, the flaws are so obvious and just lay there. Some great examples are permissions and VB viruses in that malicious code once enters the system has root level rights automatically. Also, look at those strange error messages with random codes, these codes don't actually mean anything to Microsoft as they're really machine derived codes that make no sense to anyone. Metro UI was built in this same way. The start menu no longer worked so it was simply replaced, but it's probably still there deep down in the code, just turned off. Eventually some developer of Metro Apps will hit a brick wall and they will turn Metro off and replace it with something else.
"Just works" is code for "crappy code that pays the bills"...