I remember someone saying its best to call a floor trace twice, once before c_move and then once again after c_move

Not sure why but does seem to work. Perhaps it is something to do with changing a z position directly does not perform collision detection as it does when using c_move or ent_move.

Call trace to move enemy up on terrain if result is not 0

Move player forwards into terrain (c_move)

Call trace again to move enemy up on terrain after moving forward.