I don't know that I can completely answer your question, but I can tell you that the change to using a std::multimap occurred during the last day of GrCon'14 (i.e. the hackfest day) after profiling measurements were showing that the tagged stream blocks were spending a great deal of time in the tag processing (primarily because at the time the tags were stored in a std::deque). The switch to using a multimap as the backing store provided a significant performance boost. As a side effect this may result in the tags being presented in order (I don't recall off the top of my head if std::multimap guarantees that, although I can imagine many/most implementations may store them in-order).
I don't know if GNURadio wishes to guarantee the order in the future, if, for example, we decided to change the backing store again at some point in the future. I'll let others comment on that.