With few exceptions, the military does not spend a lot of time and energy locating and capturing absentees and deserters. Except for contacting family members (usually by phone or mail), the services simply terminate their pay and benefits, enter their information into the FBI's computer, and hope they get arrested someday by civil authorities, or that they turn themselves in. The services don't send out teams of MPs or OSI/NIS/CIS agents to track them down and capture them.
The lone exception are absentees and deserters who are considered "special category." For this group, the services will spare no expense in trying to locate and capture them. These special category personnel include those who are wanted for more serious crimes, such as murder or rape; deserters who escaped from military prisons, members assigned to special mission units (such as covert operations), and members who have had access to Top Secret, Sensitive Compartmented Information (SCI), or Special Access Program (SAP) information during the 12 months preceding the absence.
Did you know there is a bounty on military absentees and deserters? So, how come all those bounty hunters you see on TV aren't running around locating and capturing military absentees and deserters? Because there is too much paperwork involved, and it doesn't pay very well.
First and foremost, the bounty hunter must receive a written request from a military service or federal law enforcement agency, requesting "active help" in apprehending an absentee or deserter. They can't just go off and capture them on their own. Then, after the bounty hunter apprehends the member and returns them to military control, they are paid either (not both): (1) a total sum of $75.00, or (2) actual, reasonable reimbursement for expenses. One certainly isn't going to make a living apprehending deserters at those rates. ( DOD Financial Management Regulation, Volume 10, Chapter 12, page 12-5, Paragraph 120110)
More About AWOL and Desertion