The base query to get all Exchange mailboxes is:

(&(&(& (mailnickname=*) (| (&(objectCategory=person)(objectClass=user)(|(homeMDB=*)(msExchHomeServerName=*))) ))))

Csvde format for this query to retrieve CN's:

csvde -f all_exchange.txt -r "(&(&(& (mailnickname=*) (|(&(objectCategory=person)(objectClass=user)(|(homeMDB=*)(msExchHomeServerName=*))) ))))" -l cn

Output of that query is simple to parse, and looks like:

DN,cn
"CN=102 Philosophy,OU=SIS,DC=ais,DC=columbia,DC=edu",102 Philosophy
"CN=210 Kent Conference Rm,OU=SFS,DC=ais,DC=columbia,DC=edu",210 Kent Conference Rm
"CN=Fred Arce,OU=Central Admin,OU=Medical Center,DC=ais,DC=columbia,DC=edu",Fred Arce
"CN=Adnan Akram,OU=Central Admin,OU=Medical Center,DC=ais,DC=columbia,DC=edu",Adnan Akram