I have users complaining that they never receive the email from NetSuite when they attempt to reset their password. Can anyone point me to where this is configured?

Don't believe you can change anything about the password reset process. You might make sure recieving email servers aren't blocking it

Is there any way I can verify if a message was sent or not?

For that one? No. For messages sent from your account, absolutely. Password reset is initiated by netsuite