After I posted that, I was thinking regex could come in handy - I just couldn't be bothered to come back and edit my post. If you want to use regular expressions, something like this might work:
:([^\s]+)![^:]*: ([^\r\n]*)
EDIT: is it me, or does that look like the most elaborate smiley ever?