However, I'm seeing a huge parade of invalid/stale results when I run the miner, with a few accepted results between them (About 80% of results are invalid/stale).
Yes, this was an temporary issue of the pool, bitcoin client crashed for no particular reason. Now it is OK.
or does the deepbit server work differently?
Yes, there is difference between those pools. My pool is analyzing every submitted share in realtime and deepbit accept all submits and analyze them later. So the fact that you see more stale shares in my pool is not a bug, it is a feature.
But yes, the thing you reported was an issue of the pool, it's without debate.