now making regular appearances at jazz festivals internationally, Hicks continued to perform in New York City. 1990–2006 Hicks divorced his wife, Olympia, in the early 1990s. The couple had a son and daughter (Jamil Malik and Naima). Like many jazz musicians in the 1990s, Hicks recorded for multiple labels proposing different recording ideas. The resultant recordings included duo sessions with Jay McShann (1992) and Leitch (1994) for the American Reservoir Records, and several trio-based sessions for Japanese labels – the New York Unit with bassist Richard Davis and drummer Tatsuya Nakamura for Paddle Wheel Records, and the New York Rhythm Machine with bassist Marcus McLaurine and drummer Victor Lewis for Venus Records. These were followed by more trio recordings for other labels – the Keystone Trio of George Mraz and Muhammad for the Milestone label from 1995, and a longer-lasting band with Dwayne Dolphin on bass and Cecil Brooks III on drums for HighNote Records from 1997. The last of these included his most commercially successful recordings, which were tributes to other pianists, including Something to Live For: A Billy Strayhorn Songbook, Impressions of Mary Lou, and Fatha's Day: An Earl Hines Songbook. There were five such albums, all linked to Pittsburgh-associated pianist-composers; the other two were Nightwind: An Erroll Garner Songbook, and Music in the Key of Clark for Sonny Clark. Hicks played on five of David "Fathead" Newman's albums for HighNote, and was described in 2000 as the "HighNote house pianist". There were also more dates as a sideman for Murray, Leitch, Blythe, Freeman, and Roy Hargrove (1989–90, 1995), Bartz (1990), Lake (1991), Steve Marcus and Valery Ponomarev (both 1993), Nick Brignola, Russell Gunn, and Kevin Mahogany (all 1994), the Mingus Big Band (c1995), Fortune (1996), and Jimmy Ponder (1997). As leader, his repertoire in the 1990s was often of familiar standards. He performed in the UK with the Mingus Big Band in 1999, and played on their album Blues and Politics in the same year. The pianist recorded the seventh instalment of the "Live at Maybeck Recital Hall" series of solo piano concerts which were recorded for Concord Records. He was part of Joe Lovano's quartet in 1998, which led to Hicks being part of the saxophonist's nonet from its formation the following year. Hicks and Wood married in June 2001. He made a rare recording on organ (Hammond B3) on saxophonist Arthur Blythe's Exhale. Over the