Virginia "Gin" Baker (Catherine Zeta-Jones) is an investigator for "Waverly Insurance". Robert "Mac" MacDougal (Sean Connery) is a professional thief who specializes in international art. A priceless Rembrandt painting is stolen from an office one night, and Gin is sent undercover to investigate Mac as the chief suspect. She tries to entrap him with a proposition, claiming that she is a professional thief herself, and promises that she will help him steal a priceless Chinese mask from the well-guarded Bedford Palace. Before agreeing, Mac tells Gin his 'Rule Number One': "Never carry a gun: You carry a gun, you may be tempted to use it." They travel to Scotland and plan the complicated theft at Mac's hideout, an isolated castle. Aaron Thibadeaux (Ving Rhames), apparently the only ally that Mac trusts, arrives with supplies for the heist. While Mac is busy making final preparations, Gin contacts her boss, Hector Cruz (Will Patton), from a payphone, and informs him of Mac's whereabouts. Little does she know that the island is bugged, allowing Mac to eavesdrop on their conversation. Mac also makes sure to keep Gin's romantic advances at bay, unsure if she is a true partner in crime or an ambitious career woman on a mission.
After they have stolen the mask, Mac accuses Gin of planning to sell the mask to a buyer in Kuala Lumpur and then turn him in. Gin convinces him that her insurance agency job is the real cover and that she has planned an even bigger heist in Kuala Lumpur: $8 billion from the "International Clearance Bank" in the North Tower of the Petronas Towers. During their set-up, Cruz and his team (with the guidance of the stealthy Thibadeaux) track down Gin and confirm that she is still on mission to bring Mac in. Despite the presence of Cruz and other security watching the building, the theft takes place in the final seconds of the new 2000 millennium countdown. Gin pulls the plug on her laptop prematurely and sets off alarms. They narrowly escape the computer vault and are forced to cross the lights hung from the bottom of the bridge linking the two towers. Following a death-defying escape when the cable breaks, Gin and Mac make their way to a ventilation shaft, where Mac explains "Plan B." Using mini-parachutes, they were going to escape down the shaft. Gin has lost her parachute earlier in the escape, so Mac gives her his. He tells her to meet him the next morning at the Pudu train station.
Gin arrives at the station waiting for Mac. He shows up late with Aaron Thibadeaux, who reveals himself with fellow FBI agents. He explains that Cruz is here and that the FBI has been looking for her for some time. Two years ago when Agent Thibadeaux caught and arrested him, Mac made a deal to help the FBI arrest Gin, as she was the primary target all along. However, the aging thief has another plan: to help her escape. Mac slips Gin a gun and quietly explains that he returned only seven of the eight billion dollars they had stolen electronically in the heist. Gin then pretends to hold Mac hostage at gunpoint, threatening to shoot him if the agents follow her. She boards a train and the FBI heads to the next station. Gin jumps trains mid-station and arrives back at Pudu. She tells Mac that she needs him for another job and they both board a train.

Question: How did Mac and Thibadeaux actually know each other?
Answer: Thibadeaux was the one who caught and arrested Mac.
Alternative answer: Thibadeaux had arrested Mac two years earlier.