SQL Server Agent job history not showing PRINT newlines

In some stored procs we are PRINTing out information about the state of the process to help with debug. It shows up nicely per line in the execution Messages tab. However as we move over to execution via SQL Server Agent, we found the job history log does not like using newline characters.

Step Name                       uspBatAggregateGenGasConsumption

Duration              00:00:00

Sql Severity                      0

Sql Message ID                 0

Operator Emailed              

Operator Net sent              

Operator Paged                

Retries Attempted               0

Message

Executed as user: IS_ELEARNING\SQLServerAgent. Last aggregated 2008/04/22 19 [SQLSTATE 01000] (Message 0)  Seeking for 2008/04/22 21 [SQLSTATE 01000] (Message 0)  Aggregating 2008/04/22 20 [SQLSTATE 01000] (Message 0)  Last aggregated 2008/04/22 20 [SQLSTATE 01000] (Message 0)  Seeking for 2008/04/22 22 [SQLSTATE 01000] (Message 0).  The step succeeded.

Even when explicit CHAR(13)+CHAR(10) variables are appended to the strings, they still clump together for the job history message log. Is there a way to get SQL Server Agent to happily accept CRLF?