My suggestion is to build a FSM with all the REs and then identify shift/reduce conflicts which will identify multiple matches. When you parse through the document you memorize the reduces and force a shift to potentially identify a longer match. This way you will only have to traverse the document once. If you have multiple matches of the same length you may have reduce/reduce conflicts, but they should be easy to identify since you can check for other reductions every time you reach one.
Another alternative is to find nested REs. Run a regex for each RE over the set of remaining REs which should be O(n log n) with respect to the set of REs. Once you find a match you take out either the matched or the matching RE and go on. If you find more than one matching RE then repeat the process saving all the sets. Once you don't find any more matches you run each of the sets over the document. In the worst case it may be more expensive than running each regex separately. In the best case, you will run through the document only once, but you'll pay a little to do regex over the REs.