To answer my own question: Following the suggestion from FrankK above, the reason I can solve my problem with pencil and paper in reasonable time when Solve takes more time than seems necessary is that I am exploiting the simple cases.
It turns out that there are eight cases to be considered, meaning that eight different ways that the constraints need to be applied. In the simplest case - #1 - Solve isn't even necessary. With case #8 I wouldn't want to try solving it with pencil and paper. Cases #2-#7 have increasing complexity, accordingly.
The next time I implement this I'll formulate some boolean tests to see which case is applicable and if it's Cases #1-7 I can simplify the constraints accordingly.
Obviously, Solve has to assume the worst case, and that - I'm assuming - is why it takes so long.