It's not easy to help you without knowledge of your system implementation. I can only make a few guesses.
First of all, the delay is in the 2us range. This short time is very difficult to manage in software.
You excluded this delay is due to higher priority interrupts, but common hw processes, like bus arbitration, memory burst accesses or other unpredictable events can lead to a non neglectable delay in this range.
What's you processor system clock frequency? Is Nios the only bus master or do you have dma?
Please also specify where the irq comes from. Is this a PIO interrupt? And how do you read the data being lost?