I run CoH in full screen on both our XP machines and in our Vista boxes... Yes we need to run in Admin mode on Vista in order for the application to be able to access the same memory space as CoH. It's also configured to run in XP SP2 compatability mode, although I don't know if that's actually helping our cause any.
I've filed a bug on HeroStats not consistently z-ordering to the top window location under Vista, but to my knowledge they've not yet figured out the fix. I do know that Vista changed the z-ordering rules somewhat and they (the HS team) were looking into that.
The work around I've been able to do (totally hacky, but it works) is to start HeroStats first. Then once it's in "in-game" mode, I start CoH, and when the splash screen is displayed, I click on it w/ my mouse periodically (like every 2 seconds or so) until I get the login prompts. I haven't nailed down where specifically I need to reset focus during the CoH load, but it appears that it does have to do with how the game loads.
Anyway YMMV, but that's how I've gotten HS to stay at the top of the z-order.