At least in wolverines case, he isn’t truly, fully, immortal. His healing factor eventually slows to the point he gets old and dies. In the case if true immortality like Mr. Immortal, it is most likely part of the power that gives them immortality to also keep the body roughly the same, i.e in working order. Mentally they all probably go insane after a few hundred or thousand years, but the comics do not cover such large periods or accurately reflect the mental state.