(.*) matches everything, so it will “eat up” the extra characters (it is “greedy”). If the URL is /tax1/foo/tax2/bar/, the first (.*) will be foo/tax2/bar/, so nothing is left for the second match.
Instead of (.*) you can use the “non-greedy” version (.+?). This will match as much as possible, but still keep the rest in mind. You can also use the even stricter version ([^/]+): this will match everything up to the next / – but this will not work for nested categories, so /category/fruit/banana/tag/flies/ will not split up in fruit/banana and flies like you might expect.
If you are going to play with the rewrite rules I recommend you to install my Rewrite analyzer plugin. It allows you to see the current rewrite rules and play with URLs to see which rules will match.