I have found that the solid operations can become flaky when there is too much complexity. Particularly when the operand of one operation is the operator in others. This will undoubtedly improve (considering the SEOs were very unreliable in 8.0, usable in 8.1, and pretty good now).
I don't have any rules of thumb yet for how much is too much or what particular conditions may lead to failure. You can probably get it to work by subdividing the site model (easiest along contours, retaining walls, etc.)
Another cause of problems could be extremely acute angles in the resulting solid, particularly cotangent curves.