I am using an bounding volume around my lights as well, but that won't work if you have directional lights. So how are you handling that type of light.
There are actually several solutions on handling this. In my case, the only directional light is the sunlight (respectively moonlight in the night), they're handled separately. As I stated in case of exterior scene the sunlight has maximal importance (e.g. it will always be rendered).
Now you need to somehow work with shadow maps for sun. In my case, I use cascaded shadow maps. For more information on them, see http://msdn.microsoft.com/en-us/library/windows/desktop/ee416307%28v=vs.85%29.aspx (or just google for "cascaded shadow maps" - there is like a TON of resources) ... and as "rendering importance" is maximal for sunlight, the "cascades" gets re-rendered, if either camera-position changes, light-position changes or dynamic object in the exact cascade has moved.
And as cascaded shadow maps cover the whole view frustum, they're perfect for simulating shadows for directional lights (note that they might not cover 100% of your frustum in order to optimize, you can cover F.e. only like 50% of your view frustum, and make your shadows disappear in the distance ~ with same number of cascades you will get better resolution of shadows near the camera). Cascaded shadow maps can (and should) be stabilized to achieve non-shimmering shadows.
NOTE: Of course if you have lots of directional lights, there is no way to do cascaded shadow mapping for all the lights at good frame rate (performance reasons of course).
NOTE 2: That spotlights can also use cone as bounding volume. Somehow limited directional light (affecting just known area of plane that is perpendicular to light direction) can also have bounding volumes (like "infinite" cylinder - it's actually finite, because you can limit near and far planes to just cover the scene).