YES

(VAR va vb ta vc vy vg vh)
(RULES
  c_union(c_insert(va,vb,ta),vc,ta) -> c_insert(va,c_union(vb,vc,ta),ta)
  c_union(c_emptyset(),vy,ta) -> vy
  c_union(c_Message_Oparts(vg),c_Message_Oparts(vh),tc_Message_Omsg()) -> c_Message_Oparts(c_union(vg,vh,tc_Message_Omsg()))
)

(COMMENT
Termination is shown by KBO with weight

  w0 = 1
  w(c_Message_Oparts) = 1
  w(c_union) = 0
  w(tc_Message_Omsg) = 1
  w(c_emptyset) = 1
  w(c_insert) = 0

and precedence:

  c_union > c_insert > c_Message_Oparts > c_emptyset > tc_Message_Omsg
)