Correct - for a variety of reasons, Tweets may not be in the public API. Performance, datacenter cache inconsistencies, and short-term search indexing are often some of these reasons.
If you need higher fidelity then the commercial Gnip solution may be more appropriate. It doesn't allow access to mentions timelines, rather a set of streaming rules that you could use to track things more clearly.
What's interesting here is that the Tweets are missing from (web) search so they may have been temporarily blacklisted or marked as spam - NB the search API uses a different index to the web search.
I'm surprised that you say the actual
user_mentions objects are missing in the Tweet object if this is pulled using the user's auth token - I've not heard of that before and I'd expect Tweets to be rendered consistently between accounts.
In terms of notifications, you might also want to look at this response, since some of the same things might apply to the mentions timeline.
I realise that this is non-deterministic and that's frustrating as a developer, but there's not many other avenues I can think of to suggest.