That is an odd problem!? Never heard that before.
Are you 100% sure your queue/list contains the actual midi events? Are there no multi-threading locking or race condition issues? Note that the host will call your plugin on separate threads.
A second option I can think of is to not output the midi during Audio Processing time, but straight in the MidiProcessor.Process method.
Also have you tried different hosts? And did they all respond the same (if so, probably a bug in your code ;-)
Hope it helps,