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 ELPO with interpretations on natural numbers

  c_Message_Oparts_A(x1) = 2438
  c_union_A(x1,x2,x3) = x1 + x2 + x3 + 1
  tc_Message_Omsg_A = 1
  c_emptyset_A = 30094
  c_insert_A(x1,x2,x3) = x1
  c_Message_Oparts#_A(x1) = 0
  tc_Message_Omsg#_A = 0
  c_emptyset#_A = 0

and precedence:

c_emptyset > c_union > c_Message_Oparts > tc_Message_Omsg > c_insert
)