std::deque appears to have the same issues that std::vector had. Does any nice person feel like implementing the same workarounds for std::deque so I can have an efficient std::stack of matrices?

You should talk to Hauke: he just implemented the fix for std::list (yes, it had a similar problem) so he might be what you call a nice person

I created an enhancement request in the issue tracker.