I have now got a Debian Xen domU running the strict SE Linux policy that can boot in enforcing mode. I expect that tomorrow I will have it working with full functionality and that I will be able to run another SE Linux Play Machine in the near future.
Read it here
Another thing I want to do is to get PolyInstantiated Directories working in Debian. The pam_namespace.so module needed for this is written for a more recent version of PAM, so I might just work on merging the Debian patches with the latest upstream PAM instead of back-porting the module to the ancient Debian PAM.