Does anyone have an example trace of a modifyItemRequest on an email
item to change the categories on that item? I'm having a hard time
constructing the right soap request in PHP to do this, so an example
how this should look like (especially with multiple categories on a
single item) would be very much appreciated.

I'm especially curious how the <categories/> part should look like.

Thanks in advance,