Ok, this might be kinda hard to describe, but I'll try my best.
Is there a way, short of dual booting or reinstalling Windows, to run x86 programs in an x64 environment? Example: I have a few older games lying around, but I can't install them because they are x86 compatible. But I can't use DOSBox to run them either, because they are Windows Executables.
So, is there any program that can allow me to play them without screwing about with a dual boot? I'm low on actual HD space and I have over 2.5gb of RAM installed, so I it's pointless for me to switch back to x86.

Microsoft VirtualPC , Sun Virtual Box* are both free, you can load a 32bit Windows into a virtual environment and play them. (You will need a license and copy of course). They do require a fair bit of HDD space.
Performance may vary, depending on what is 'emulated' in the environment and the games requirements.
and more: listed by Qbix

Thanks for the advice. I'll probably wind up getting Windows Virtual PC 07 and use my old copy of XP for the install. Now to clear out space :P

Actually, x64 versions of Windows already come with this. There's a 32-bit subsystem called WOW64 that is used automatically whenever you run an x86 application. But seeing as you are asking this question, WOW64 must already have failed to work, in which case:
...would be your best bet. These require a complete installation of a 32-bit Windows inside the virtual machine though, so you will need some amount of hard drive space. Also, I'm not sure that 3D acceleration will work (can someone confirm this?)

...hence there is little or no advantage in using those instead of a dual-boot. Also, 3D acceleration either don't work at all or work poorly.
You best bet would be WINE, but dunno, if it works in Windows.

VirtualBox and VMWare have added experimental support. These are, to my knowledge the only two that have any support at all.

Are to problems you are having with these occuring when trying play them or install them, because in my experience Vista 64 have very few problems running 32 Bit executables but, it is completey incompatible with the 16 Bit installers most old game use.
So if the problem you are having is getting the actual installers to run, than aside from a dual-boot setup you could try copying all of the data from the disk to your hard drive and running the game executable from there. This bypasses the 16 Bit installer and since most old games don't make much use of the registry so it could work, at least that is how I got my copy of Commandos: Behind Enemy Lines running.

It doesn't, at least not in VirtualPC or VMWare.
Always thought that if Nvidia would release an emulator to interpret old commands into ones fully compatible with new GPUs, it'd solve a hell of a lot of issues, might even be worth buying as a commercial product but that would set a precedent that could be pretty easily abused

The game in question is Dark Seed II. I copied the files from the CD to a separate folder on the HD, and tried running both the setup file and the actual game exe. Both files, when run, give me the same error seen in the pic

Tried win95/98 compatibility mode?

Ah, that explains it. The error message you posted indicates that the files are 16 bit executables, which work fine in 32 bit versions of Windows, but not in 64 bit mode. I doubt that Windows 95/98 compatibility mode will work in this instance.
From what I remember it's not a Windows-related limitation, it's a limitation in the x86-64 CPU instruction set. (With a 32 bit OS you can only run 16 bit and 32 bit applications, with a 64 bit OS you can only run 64 bit and 32 bit applications)
According to Wikipedia, the game was released for Windows 3.x. This confirms that the executables are 16 bit, and is good news because:
- That means the game doesn't use 3D acceleration, so emulation/virtual machines should work well
- If you run Windows 3.x in a virtual machine, you only need a fraction of the drive space needed for an XP or Vista VM
- You can use Dosbox, which is a free virtual machine. Newer versions of Dosbox can run Windows 3.x (and 95 as well)

VirtualBox's 3D support is probably the most developed at the moment. Only a few games work but performance is quite good (especially if you have a CPU that includes hardware-assisted virtualisation technology). DirectDraw games will work better than Direct3D ones, although DirectDraw games are more likely to run fine natively anyway. Unlike previous implementations it supports the real DirectX 9 data files, not the incomplete WineD3D replacement, so once the renderer is able to support a fuller feature set its compatibility will much more closely match that of a real system.
That won't help; that error is specifically triggered when running 16-bit software on a 64-bit OS or 64-bit software on a 32-bit OS. Unfortunately some sort of emulation or dual boot setup is the only solution.

I'll probably wind up going the 3.1 route, since DOSbox can't open windows executable's, and DS2 doesn't have any DOS files anywhere.

Note that you can install Windows 3.1 in DOSBox and then run 16-bit Windows software within that. It might not support certain advanced display modes and such yet but it should work just fine for simpler games and it's a bit easier than using a VM.