Change all new-line characters to something else
tr "\n" "~"
Change all ctrl-Z to new-line
(I think ctrl-z is octal 32, so...)
tr "\32" "\n"
All the messages would now be one per line. Thus, you could use head and tail commands to break apart the file.
When done, reverse the previous two steps.