Voice-mail does work on a Verizon Galaxy S7 Edge, I have received at least 10-15 Voice-mail since I owned my S7E...I have owned mine about 20 days or so.
I don't see any way voice mail is handset dependent. It purely carrier system controlled. You don't even need your phone. You can retreive voice mail from any phone. You can smash your phone to bits and still get your voice mail