I'm wondering whether it's safe to mark bounce messages containing "This is a permanent error." string from the first time?
When I get "This is a permanent error." doesn't mean "permanent error" for this message or for the user?
Depends on what the error code is. Check the message for a code, and compare it to one of these tables, which should tell you more.
http://www.unixhub.com/docs/email/SMTPcodes.html
http://www.emailaddressmanager.com/tips/codes.html
Without the actual error output, I can't give you a more specific answer.