In a government reshuffle in 1999, Scotland was appointed Parliamentary Under-Secretary of State at the Foreign and Commonwealth Office. She was responsible for the British overseas territories, and also relations with Southern Asian countries. She was responsible for introducing the Bill to ratify the International Criminal Court in the United Kingdom. She also established a panel of British-based lawyers who gave their time on a pro bono basis to United Kingdom nationals imprisoned in foreign countries. In 2001 she became Parliamentary Secretary, Lord Chancellor's Department, and was made a member of the Privy Council. Scotland was a contender for a cabinet position in 2003, when Tony Blair reportedly considered appointing her Leader of the House of Lords .
In 2003, Lady Scotland of Asthal was made Minister of State for the Criminal Justice system and Law Reform at the Home Office. A new extradition treaty with the United States of America had been signed on March 31, 2003. Scotland had the responsibility for promoting the necessary legislation in the House of Lords. . In 2004 Scotland was suggested as a possible appointee as a Commissioner of the European Union.
The 'NatWest Three' extradition case directly connected to the treaty was unusual in that the offences the three were charged with are not typically extradition offences. The three men are all British citizens, worked and lived in the UK for the Royal Bank Of Scotland and the NatWest Bank, both British banks. The UK ratified the UK/US extradition treaty of 2003 while the US has still to bring the legislation into law. On 12 July 2006, in a highly unusual move, the Speaker of the House, Michael Martin, allowed an emergency debate on both the treaty and the 'NatWest Three' after a request by Liberal Democrat frontbencher Nick Clegg. During the debate Lady Scotland of Asthal's view in 2005 that a higher threshold to establish 'probable cause' was required by the UK to extradite from the US than vice-versa was contrasted by Clegg to comments the Prime Minister had made in July 2006 in which he stated that the evidential burdens on the two countries were the same .
The NatWest Three were duly convicted of wire fraud in the United States.