Remove a category :

<UPDATE>
  <MEDIA ID="25">
    <CATEGORIES operation="remove">
      <CATEGORY ID="12"/>
    </CATEGORIES>
  </MEDIA>
</UPDATE>

You can also use the path of the category :

<CATEGORY path="/contact/newsletter/"/>

or its uniquename :

<CATEGORY name="newsletter"/>

Be careful about the spelling.

If you want to remove all categories of an element :

 <UPDATE>
  <MEDIA ID="25">
    <CATEGORIES></CATEGORIES>
  </MEDIA>
</UPDATE>

You can also remove all the subcategories of a same parent category :

<UPDATE>
  <MEDIA ID="25">
    <CATEGORIES operation="remove">
      <CATEGORY fatherID="11"/>
    </CATEGORIES>
  </MEDIA>
</UPDATE>