New functionality in Blender 2.49
Until Blender 2.49, a Boolean modifier could only be used at the beginning of a modifier stack. In 2.49 you can put it on any level in the stack, allowing you to intersect deformed or subdivided models too.
Another new possibility resulting from the enhancement is that you can also use the Boolean modifier multiple times, e.g. 3 times in a row, on the modifier stack. So you can keep your non destructive workflow without having to apply in between.
Last but not least, Blender 2.49 also enables you to use objects for the boolean operation (target objects) which also have modifiers on their stack. Imagine a subsurfed targed object subtracted from your base object - not a problem anymore!
This enables you to perform even more complicated objects dependancies within a non destructive workflow.
You can test the new boolean tool possibilities using this blend file: Boolean enhancements example
Video showing the new Blender 2.49 workflow:
Booleans still have to be used with care; only well structured Mesh models will give good results. Make sure you use Manifold models, like closed volumes, with normals pointing outside. Intersections with planes won't work well.