Yes, verification must be intensive. Indeed, it's much more important that the verification is intensive than the original generation. (It's hard to see how you'd have cheap generation and costly verification, but that would be okay.)
The point is that if it's cheap to verify a password, then an attacker can check lots of passwords quickly. If you make verifying each guess costly, however, it becomes much less feasible to apply brute force to cracking a password.
Even though the verification is relatively expensive, it's still unlikely to be a very significant cost in the operation of a normal application, unless you're under attack (at which point you don't want to be verifying things quickly). If you're getting enough legitimate login attempts to cause your server to break into any kind of sweat, that suggests you've got enough users that you can probably afford to scale out somewhat...