Erste Hinweise könnte dieses Händlerangebot geben:

http://www.briefmarken12.de/deutschland/bund/messebelege.php

Start der Messebelege war in der Tat 1994, wie einige Internetangebote wie dieses hier ausweisen:

http://www.ebay.de/itm/Bund-Messebelege-1996-Komplett-3-Jahrgang-25446-/360525816603?pt=Briefmarke&hash=item53f103631b

Ich erinnere mich an einen in Bielefeld ansässigen Spezialhändler, der sich jedoch im Netz sehr rar macht. Sollte der eine Angebotsliste versenden, entspräche dies wohl weitgehend der gewünschten Aufstellung.