This is the result of RTC's allowing you to "deliver baselines" (I believe it should only allow you to "accept" baselines, to avoid this behavior).  Work item Provide simpler and more predictable stream baseline history (286482) was submitted to get this behavior changed.

Warning: You will probably need to draw the following on a whiteboard to follow along (:-).

Suppose that your workspace starts being in sync with your stream.   Now you create some change sets in your workspace and baseline them (with BL23).   At the same time, some other user has created some other change sets in their workspace, created a baseline (BL44), and delivered that to the stream.   So in your Pending Changes view, for your workspace, you will be seeing an outgoing BL23 and incoming BL44.   So far so good.  But now, suppose that you deliver your changes to the stream.   The only way to deliver BL23 to the stream is for the server to effectively suspend the change sets in BL44, deliver BL23 to the stream, and then resume the suspended change sets.  But now note that BL44 no longer exists in the change set history of the stream (because there is no point in the change set history of the stream where you have just the changes from BL44 and not the changes of BL23.  So what do you then see in your Pending Changes after you deliver?   BL23 now exists in the stream, so you have no outgoing changes.   But if you look closely, you will notice that you no longer have an incoming BL44 baseline ... because BL44 no longer exists in the change set history of the stream ... instead, you see all of the change sets of BL44 as incoming change sets.  A little strange, but you'd only notice if you had opened your Incoming changes folder, and noticed that your Incoming folder had changed even though you hadn't accepted anything from it, and nobody had delivered anything new to the stream other than you.   But in that other user's Pending Changes view, something very strange has happened.  Their outgoing changes folder which had previously been empty, now contains BL44 again!   And if you open up BL44 in the Outgoing folder, you'll see there are no change sets there!   Well, that is because all of the change sets that the other user had delivered to the stream are still in the stream ... but BL44 is no longer in the change history of the stream.

So what do you do to prevent this kind of confusion?  
One way is to not create baselines in your workspace, but instead, create them in the stream.   Then you will have no outgoing baselines that will reorder the change sets in the stream and remove baselines from the change set history of the stream.
Another way is to always accept incoming baselines before delivering your baselines.  When you do that, any baselines that you have defined in your workspace will disappear from your Outgoing folder (not because they have been delivered to the stream, but because they no longer exist in the change set history of your workspace).  That way, your deliver will not cause any previously delivered baselines to disappear from the stream.

WRT your follow-up observation ... this is a different issue, but related.   Because you can make baselines disappear from the change set history of a stream/workspace, the system needs some way of remembering what baselines were in that stream/workspace at some previous point.   So in addition to the change set history, it maintains a "baseline history" for the stream/workspace, which is all of the baselines that were accepted/delivered/created in that stream.  Because a baseline can disappear from, and then be added back to, a stream/workspace, this means that a given baseline can appear multiple times in the baseline history.

 I say that this observation is just "related" because there are other reasons that accept/deliver for a baseline being removed from the change set history of a stream/workspace.   In particular, you can use the "replace" operation to jump to a completely different baseline.   So even if the accept/deliver behavior was changed ("fixed" :-), you still would need to maintain the baseline history, for the stream/workspace to remember its state before the replace occurred.