For outgoing messages there's no Categorize button.

Whatever that should be good for, for OL 07 it was decided that no outgoing
message needs a category. At least, they do it strictly: Replies, forwards,
meeting- and task request also don't get the category from the original
item.

So, at present you have to add the category manually each time. You could
shorten the time for doing that by having your categories permanently
displayed in a side-bar: The addin Category Manager provides you with that
feature and even allows to filter the category list (see link in my
signature).