I think Jesse's answer is basically right, but I thought it worth offering a slightly different perspective, just for more dimension.
I think Jesse is correct that 殿{どの}
used to be more decidedly respectful than it is now. It used to represent a specific place in the social hierarchy. However, it's not so much that 様{さま}
has overtaken it, just that 殿
has been regulated to very specific situations. Formal letter writing, certain business interactions, and so on.
So it's not the case that you would meet someone on the street and opt to use 殿
to convey you respected them less than 様
but more than さん
.
With that in mind, one could argue that it's not necessarily less respectful than 様
, just different, regulated to being prescribed in specific ritualized situations.
I think 殿
is somewhat archaic, and given that you can, as I mostly have, go years without having to use 殿
, I would suspect it might be slowly getting phased out.