[Mark McLeod]

We usually design for under 10,000 interrupts per second (5K last year), but we have tested with more at free wheeling speeds.

It isn't just the speed of the processor but the efficiency of your fast loop code and what else you attempt to do in there that will determine your limit. In extreme cases if your slow loop is so bloated that it pushes 26ms, then you'll be seriously impacted.

I'd measure the time of your fast loop with an internal timer or with a scope attached to a digital output that you reverse every loop. The loop times will vary based on the semi-random combinations of high/low interrupts, etc. I'd take the slowest time measured and cut that by 50% or more as a safety factor to determine your maximum acceptable interrupts per second.
If you're real ambitious you can even model the interrupts you will be adding by including some extra processing delay equivalent to the rate you choose to design for.

I'd also measure again after you implement to be sure you're still within your self imposed spec. as regards loop time.