When their U.S. mainland to South America flight was canceled due to a maintenance issue; a B767-300 flight crew was reassigned to a technically legal but much longer duty day; a three segment (DHD; ferry; revenue flight) itinerary; which proved predictably and excessively fatiguing.

Narrative

When I entered the cockpit after briefing the flight attendants; Maintenance approached me and said that there was a maintenance issue that had to be addressed before departure and that he wasn't sure how long it would take. He then stated that a part in the rudder may be missing and that he had to verify it before we could depart. After sending a note to Dispatch about our issue; they responded that Contract Maintenance had not installed the rudder hinge spacer and that structural damage had been found during an inspection as a result. Our flight was then canceled and the aircraft was taken out of service. The airplane had flown on three or four segments before the discovery was made. We were very thankful and lucky that we didn't take the jet to South America as planned.We were then assigned to deadhead off line to ZZZ; ferry another aircraft back and then fly the red eye return to ZZZ. Although the reassignment was legal; there appeared to be little or no consideration of fatigue issues. We departed ZZZ about the time we were to have arrived in South America on our original flight. It was a difficult flight as both crew members were exhausted upon arrival.