It must resolve on all clients, not the server.
Here's how namevhosts work:
1. Web browser gets
http://foo.example.com
2. Resolves to IP address a.b.c.d
3. Connects to a.b.c.d and sends the request including a line with Host: foo.example.com.
4. Webserver sees that the request is intended for foo.example.com and uses the appropriate vhost. That Host: line makes all the difference.
If the client cannot resolve the vhost domain name, it doesn't get past step 2.