From my somewhat limited experience, VIS should only take a minute or two. What I experienced was a sharp increase in VIS time when adding things like stairs without planning for optimization.
This guide:
http://www.student.ru.nl/rvanhoorn/optimization.php?chapter=intro
I found to be really helpful, although it could just have been reading and reading about optimization until it finally made sense.
The key is to visualize your map in boxes. What VIS does is divide your map up into sections based on drawing lines from the brushes you have in your map. Thus you make everything that doesn't obscure large parts of the map into func_detail entities. These interact with light but are ignored for the VIS process. It also helps to keep all brush sizes under 1024, because they get broken up anyway if you don't. Use the nodraw texture to create pretty much everything, and then use shift+a and manually selecting faces to apply textures on only what is visible. Use the clip tool rather than the arch tool in order to keep things on the grid lines. Don't make your map one large arena; even if it is entirely outside, only use skyboxes where you have to and make sure to have corners that obscure other areas. All of this keeps your VIS times low, and your framerates high.
Hopefully some of that makes sense; I'm just starting to understand it myself.