Old VirtualPC (before Microsoft buy Conetix) works on every Windows OS. I tested it on a Win98. VMWare never works on Win9x, only NT kernel OS.
Old VirtualPC (version 5 or earlier) uses .vxd or .sys pedending of kernel. I think using full CPU emulation is only one possibilty to create working x86 virtual machine. So operation on Ring0 is required.
And think about target-system-independent mode (real, protected or V86).
BTW why VirtualPC don't work on Win2k3? I didn't test it but if it really don't work - we can use Microsoft Virtual Server 2005, specially designed for 2k3.