If they don't have phones you don't need to worry about CUCM licenses, though I would recommend few in case some phones are required.
For voicemail you can simply order Unity user mailboxes - UNITYCN10-STD-USR, then on CUCM you just need a wildcard CTI Route point, etc to point all of the DIDs to voicemail. CTI RPs, Translation Patters, etc do not require CUCM licenses.