If the failures are because you're capturing data from another domain, it would not cause SignalTap to not trigger. I've seen this done and just makes the data "inexact". For example, if you're capturing a bus of data from another domain, you might have cycles where some of the bits are new data and some is old, making it very hard to read. Hopefully you're sampling with the faster clock. But as long as you know this, you can possibly weed through it. Just remember anything crossing domains is "suspect".
Are your triggers in other domains? THat might cause problems, but I would it expect it to be sporadic, not a constant failure.
In general, SignalTap should meet timing pretty easily on its internal stuff that it runs off of. I've never seen timing issues make it not trigger. I'm assuming the two are unrelated, although it is possible they're not.
Has SignalTap ever worked?