O'Haire was sent to the developmental territory in early September 2001, and Palumbo was thrown out of The Alliance in late October by storyline co-owner of The Alliance, Stephanie McMahon. He re-joined the WWF in November.
When he returned, Palumbo found a tag team partner in Billy Gunn. Palumbo became known simply as Chuck, and he bleached his hair blond to match Gunn's.
On the February 2, 2002 edition of SmackDown!, Billy and Chuck defeated Tazz and Spike Dudley to win the World Tag Team Championship. They lost the tag team gold to Rikishi and their stylist Rico Constantino, who was forced to team with Rikishi on May 19, 2002 at Judgment Day. Less than a month later Rico helped Billy and Chuck recapture the title, but they later lost it to Edge and Hulk Hogan.
In the late summer of 2002, Billy and Chuck were the source of controversy when Chuck apparently proposed to Billy on September 5, 2002 edition of SmackDown! asking him to be his "partner for life". They had a marriage ceremony on the 2002 season premiere of SmackDown!. When Billy and Chuck decided not to go through with the marriage, Rico turned on them by helping Eric Bischoff and 3-Minute Warning attack the duo. Rico subsequently jumped to Raw as the manager of 3-Minute Warning, who beat Billy and Chuck at Unforgiven. Billy was injured in early October 2002, and Chuck worked on Velocity for a few months using his original ring name Chuck Palumbo once again.
In February 2003, Palumbo formed the Full Blooded Italians (F.B.I.). After a beating at the hands of Rikishi, Nunzio threatened to bring in his "family" in order to gain revenge. The next week, Chuck Palumbo and Johnny "The Bull" Stamboli joined Nunzio to form the F.B.I. and attacked Rikishi. This version initially gained little success, but would go on to have brief feuds with Los Guerreros, Chris Benoit, Rhyno, Brian Kendrick, Nathan Jones, the APA, and The Undertaker.
Palumbo was traded to the Raw brand on March 22, 2004 along with A-Train in exchange for Rico and Jackie Gayda. After Palumbo was traded to the Raw brand, he was kept off television until July 2004, when he debuted as Custom Chucky P with a new look and entrance music. His new image resembled a cross between an auto mechanic and a greaser. It was not long before Palumbo was a regular on WWE Heat. His new gimmick started off as a jobber but began to rise on Heat, defeating the likes of The Hurricane, Rosey, Val Venis, Ollie Young, and Stevie Richards. Palumbo was later released by WWE on November 4, 2004.
During March 2006, Palumbo began working dark matches for both brands of WWE. He continued to wrestle very sporadically at house shows and in dark matches over the next year. On April 30, 2007, Palumbo defeated Kenny Dykstra in a dark match on Raw and debuted a new biker gimmick based on his real life love for motorcycles.
Palumbo officially returned on the May 25, 2007 edition of Heat (retaining the biker gimmick, as well as growing his hair out). Chuck would be heavily criticised for 'stealing the Undertaker's former gimmick' where he also rode a bike during his entrance and both donning a biker gimmick. He defeated Charlie Haas. He would then make appearances on Heat, defeating jobbers. On July 6, 2007, Palumbo made his return to SmackDown!, defeating Kenny Dykstra.
Palumbo began a storyline with Michelle McCool, which led to a scripted rivalry with Jamie Noble, after Noble made advances towards Palumbo's "girlfriend" McCool, with Noble winning two consecutive matches. In their third encounter, Noble won a date with McCool, after her inadvertent distraction led to Noble winning the match. Afterward, Palumbo blamed McCool for the loss. On the January 4, 2008, episode of SmackDown!, McCool was pinned by Victoria in a mixed tag match, also featuring Palumbo and Dykstra. This loss gave Palumbo his fourth loss in a row and Palumbo again blamed McCool for the loss. The following week on SmackDown!, Palumbo again faced Noble, this time in a Royal Rumble qualifying match. Noble again beat Palumbo, giving him his fifth loss in a row. After Noble left the ring, Palumbo attempted to take his anger and frustration out on McCool, which brought Noble back out, and he distracted Palumbo long enough for McCool to get out of the ring. On January 26, a double turn started as Noble checked on an injured McCool and Palumbo attacked him, become a villain, while Noble would turn into a face character. On the next SmackDown!, Palumbo apologized to McCool, but she slapped him, leading to him vowing to get revenge on Noble. He defeated him the following week, before the storyline abruptly ended.
As part of the 2008 WWE Supplemental Draft, Palumbo was drafted to the Raw brand. He never made his return to the brand however, as he was released from his WWE contract on November 7, 2008.