Hm, hm..... I think it's in the printf format, because /usr/bin/mail just sends already formatted message to e-mail address specified. Sendmail and exchange don't format mails. Is the mail subject formatted correctly when you get email?
If I put the command (in shell) like this (with qoutes ending before any \n and starting after \n):
/usr/bin/printf "%b" "***** Nagios ***"\n\n"Notification Type: $NOTIFICATIONTYPE$"\n\n"Service: $SERVICEDESC$"\n"Host: $HOSTALIAS$"\n"State: $SERVICESTATE$ for $SERVICEDURATION$"\n"Address: $HOSTADDRESS$"\n\n"Info:"\n\n"$SERVICEOUTPUT$"\n\n"Date/Time: $LONGDATETIME$"\n\n"ACK by: $SERVICEACKAUTHOR$"\n"Comment: $SERVICEACKCOMMENT$"\n | /usr/bin/mail -s " $NOTIFICATIONTYPE$ alert $NOTIFICATIONNUMBER$ - $HOSTALIAS$/$SERVICEDESC$ is $SERVICESTATE$ **" $CONTACTEMAIL$
I get mail in this format:
***** Nagios *****nnNotification Type: $nnService: $nHost: $nState: $ for $nAddress: $nnInfo:nn$nnDate/Time: $nnACK by: $nComment: $n
which is very similar to yours. Those $ and $nHost: etc. are such because I've just c/p-ed the command from commands.cfg to the shell, modifying just mail address at the end.
Be sure you have correctly written the command like the one I c/p-ed in the earlier post (with doubleqoutes just in front of the message and at the end).
Can you post your notify-by-email command definition from commands.cfg?