Per missingno's request, I'll answer my own questions to let future viewers know how we eventually solved this problem.
While I really liked Roger Attrill's proposalproposal for some reason it was not a good match for our application. Mainly because such a control would have taken too much space while our application needed to be small to be used side by side with other applications such as MS Word.
What we eventually implement was a UI whit two listbox (not combobox). This way the user could select the category and sub-category in two clicks instead of four. We also pre-selected the most used category by default and when a category is choosen, the most used sub-category is also automatically selected. So most of the time only one clic is needed.
We also added a zone with 3-5 buttons (depending on their size) with the most used combinations (category/sub-category) for the current job. These buttons allow the user to select one of these category/sub-category in one clic.
It's not really a creative solution, but I think that given the constraints we had it works well.
