Until the reforms in 1996, allzu… was one word: allzuoft, allzuschön, allzugroß, allzuviel, etc. But yeah, probably would have written such a long word in two words even then.

My new proposal would be überregelmäßig. Über+adjective is still one word only, post-reform. Sounds strange, but grammatically correct, and still conveys the “unusual” part.