it depends on a couple things. Remember, a disk check is checking all data on the disk so....
1. If you have a lot of users that leave old messages in thier vm box...this will increase the time to boot because voice messages are stored as .wav files and take up a decent amount of space.
2. If you have a lot of old versions of software remaining on the nbx, this will increase the boot time (most these packages are more than 60mb's in size.
A normal reboot to me is when the system does not do a disk check and on a 15-20 users system, this should not take more than about 5 minutes.
Chris