I've worked in several different fields: financial analytics, network monitoring, enterprise storage, and most recently electronic design automation. Each of them has involved different sets of formal theories. Sometimes combinatorics has come in handy, sometimes relational algebra, sometimes binary arithmetic, and so on.
Off the top of my head, I can only think of two that have been universally useful in all of them, and they have been very useful too. Graph theory comes straight to mind, and the only thing that might rival it is automata theory (including formal languages).
Graph theory and automata theory often prove to be useful even in problems that aren't conventionally thought of as graph problems or automata problems, but once you get a good grasp on them, you start to recognize patterns in problems (or sub-problems) that naturally lend themselves to elegant solutions if the problem is re-framed from the perspective of the appropriate theory. I've wound up on several projects where the requirements seemed really complex and gnarly at first glance, but we would be able to create successful, maintainable, extensible systems whose architectures essentially consisted of a chain of ETL ⇒ {graph,automaton}+ ⇔ UI — basically the same shape as the conventional compiler pipeline but applied to data, and sometimes interactive.
Graphs are extremely versatile as data structures, with well-studied properties, subtypes, and algorithms. Automata are similarly versatile as models of processes, and similarly well-studied.
The two are easily combined. One project in particular would take in a set of rules from the user, construct an automaton out of it, feed data through it, which would generate yet another automaton that doubled as a digraph. This autographaton modeled the control flow of the former automaton during execution, amenable to graph algorithms (search, flow, sort, pattern matching, etc.), arbitrarily modifiable by the user, and executable to generate an arbitrary amount of mock data that had the same characteristics (as defined by the input rules) as the data that it characterized. It was designed to aid in the analysis and simulation of network traffic, but it wound up being general enough that people in other parts of the company started using it for other things, too (that I knew of at the time I left the company: I/O loads, software testing, and automated bug report arbitrage using core dumps).
You could probably write such a program without any understanding of the theories involved, but I think that knowing the theories had some definite benefits. The theories led the program to be structured in a clean, elegant, modular, and straightforward way. They helped the program be general yet powerful and useful. Importantly, they helped the program to operate in such a way (and to present such an interface) that was intuitive for the tasks—and the people—it was designed for. I absolutely credit the solid theoretical foundations with the success of the program, and I've gone on to design programs with similar foundations yet intended for different sorts of tasks—and people—that have also been rather successful, though, admittedly, perhaps not so generically applicable.