Their 1990 follow-up "Gumbo Millennium" was not as successful as "Harder Than You" and debuted at lower position at #135 on the Billboard 200. However, it did manage to sell over 300,000 copies. Shortly after the release of "Gumbo Millennium", vocalist P. Fluid and drummer Anthony Johnson both left the band, citing musical and personal differences. They were replaced by Jeff Brodnax and Joel Maitoza on vocals and drums respectively. Also during this period, 24-7 Spyz were dropped from In-Effect/Relativity and signed to East West Records America. The line-up of Brodnax, Hazel, Skatore and Maitoza recorded the "This Is...24-7 Spyz!" EP in 1991, which was followed by their third full-length album "Strength In Numbers". Although both releases failed to chart, its singles "Stuntman" and "Break The Chains" enjoyed moderate success on MTV. After 24-7 Spyz got dropped from East West, Brodnax and Maitoza left the band.
1994 saw a reunion of the classic lineup featuring Fluid, Hazel, Skatore and Johnson. This lineup recorded the band's fourth full-length album "Temporarily Disconnected", which was released in 1995. The album was released exclusively in Europe by the Enemy label, but failed to match the success of their previous releases. After touring in support of "Temporarily Disconnected", Fluid and Johnson left the band once again. Maitoza rejoined the band, and instead of hiring a replacement for Fluid, Hazel took over the vocals duties while still a guitarist. Now a trio, they released their fifth album "Heavy Metal Soul By The Pound" (also known as "6") in 1996. However, Maitoza was replaced by Matt Martin and later Tony Lewis. Although "Heavy Metal Soul By The Pound" helped reignite the band's popularity in Europe and the United States, personal tensions and disagreements between Hazel and Skatore surfaced, which resulted in the end of 24-7 Spyz.
After five years apart, 24-7 Spyz reformed in 2003 with the 1998 lineup of Hazel, Skatore and Lewis. However, Lewis left the band in 2004 and was replaced by current drummer Tobias Ralph. After playing a series one-offs, the band eventually recorded an album, "Face The Day", released in July 2006.