An employee has this message on his employee record. What happens if i press "remove bounce entry". The same person also gets promted for security questions whenver he logs in.

That actually might explain your security questions prompting every time. I'd be tempted to remove bounce entry - remove the email address from the employee - and then add it back.

I have seen this when the address is also being thrown in the email marketing campaigns. It gets to a point that the email client blocks emails from netsuite. Clean up the bounce list and error should go away, but also be sure to filter out employees from email blasts or this will keep happening