Despite Khurram's performances, the UAE finished fifth at the tournament, and failed to qualify for the 2003 World Cup. Khurram was named captain for the ICC Six Nations Challenge in March 2004, a qualifier tournament for the ICC Champions Trophy, and though Khurram was once again leading wicket-taker for the UAE, the team finished fifth on net run rate, coming last after four other teams on points. Khurram was retained as captain for the 2004 Asia Cup, however, where the UAE took on the Test nations of India and Sri Lanka. They were eliminated after two group stage matches, though Cricinfo claimed that he and his fellow team-mates "bowled with plenty of discipline and control"  in the first match against India, and "a maturity far beyond their experience"  in the second match. Khurram got one wicket in his first match, with the last ball of a ten-over spell, and took four for 32 in ten overs against Sri Lanka, including the top scorer of the innings Avishka Gunawardene who lofted a catch to the deep for 73. He was the leading bowler as Sri Lanka were bowled out for 239, but only contributed with eight runs in the chase as UAE were bowled out for 123 and knocked out of the tournament.
Khurram has played four matches at the ICC Intercontinental Cup, three in 2004 and one in 2005, scoring 329 runs with four fifties and taking eight wickets. He has not been the leading wicket-taker in that tournament, with Ali Asad outperforming him with 35 scalps in five matches. Khurram was, however, captain at the 2005 ICC Trophy, leading his team to a fifth place play-off where the winner would qualify for the 2007 World Cup. After bowling eight overs without a wicket at the Dutch batsmen, Khurram was dismissed for six in the UAE's total of 142, and the UAE lost by 143 runs to miss out on a World Cup berth. Three months later, Khurram had to declare himself unavailable for the semi-final of the 2005 Intercontinental Cup, with Arshad Ali captaining the side in his place.