In my experience, the easiest way to handle this painful reference requirement is to ignore it and pretend that the standard categories are only about traversal. I've never had anything break because of this.
Is the OP's problem not an example of pretending that the standard iterator categories are only about traversal and having something break as a result?
As far as I can tell, the OP's problem only appeared when he started using boost traversal iterator categories, and things were working fine when he had random_access_iterator_tag (violating the reference requirement).
Well, you didn't say anything about using standard iterator categories in lieu of Boost ones when using Boost classes like iterator_facade. If you're saying that doing that together with ignoring the reference requirement has kept you out of trouble, I take your word for it :) Regards, Nate