With Kraken the verification is instant (at least tier 1 & 2) once you enter your personal information your account is automatically updated. This how it worked for me, but the process may have changed since.
What's the difference between the first two tiers and the higher ones exactly? In most cases it's the withdrawal limit and fiat deposits/withdrawals, but Kraken might be a bit different. That being said, Kraken has been suffering from major outage problems for quite a while now, and as long as that isn't taken care of, it's not really an exchange people should work with.
Have you tried Bitstamp? Because I have a friend who has been verified in 24 hours. (it was about 2 weeks ago).
That's insanely fast. In more realistic terms, it is a pretty decent job if the verification request by Bitstamp is approved within five working days. Major annoyance is that they quite often want higher res ID scans, which only further delays the verification request, so the friend you're talking about has had the best of luck on his side.