I would also have the client check their spam folder. A lot of times that's where things end up. If there are no entries in their apache error_log, then at the moment I'm at a loss. But if you can send yourself a test email successfully (from either Drupal or just plain ol' PHP) then it's most likely something with their email, and not the system.

Also, if this only happens with one (or a small number) of clients, but not all of them, then that makes the possibility more likely.