Your difficulty may be arising because the rows sent down the "no match" output are not immediately added to your lookup table. It has to do with buffers. The rows that "don't match" are not passed on immediately to the components you have ready to add those rows to your lookup table. They accumulate until the buffer is "full", or until all rows have passed through the Lookup component. This behaviour makes the SSIS Data Flow very efficient, but doesn't make your design work - or work reliably.
You'll need to use a Cascading Lookup pattern, as
Matt Masson describes on his blog. However, even given that pattern, I'd expect similar behaviour to what you've seen so far... but I'd read that over and try it. At the very worst, you'd have to do a "double-check" in the Script that's presented there to make sure the row wasn't already added to the lookup table.
lookup transformation using partial cache mode
