"These arrests are totally unacceptable. The government is punishing humanitarian workers for doing their job for the victims of the conflict in Darfur," Geoff Prescott, director of MSF-Netherlands, said in a statement.
In a recent report entitled "The Crushing Burden of Rape: Sexual Violence in Darfur," the charity outlined that 500 women had been treated for rape in four and a half months in the western Sudanese province.
They said they were attacked by militias or armed men.
The international body Human Rights Watch (HRW) called for charges against Foreman to be dropped and urged donor governments as well the United Nations to "condemn the Sudanese governments arbitrary arrest and intimidation of aid workers".
The Sudanese arrest warrant is thought to have been issued after Foreman refused to hand over evidence on which the March report was based.
Foreman, who has been accused of crimes against the Sudanese state, was being questioned again on Tuesday, an aid source told AFP in Sudan on condition of anonymity, while Hoedt was being sent from the Darfur provincial capital Nyala to Khartoum.
"We don't know whether he is being escorted by the security and the authorities ordered that he would not be accompanied by any MSF staff on his trip to the capital," an MSF official said.
The group, whose name means Doctors Without Borders, was also accused of "espionage, publication of false reports and of undermining the Sudanese state," following Foreman's arrest, MSF's Dutch branch said in a statement.
The UN's special envoy for Sudan, Dutch diplomat Jan Pronk, was due to meet Sudan's president Omar al-bashir Tuesday, and was expected to discuss the arrests, said Bart Rijs of MSF-Netherlands.
Louise Arbour, the UN High Commissioner for Human Rights, urged the Sudanese government to allow aid workers to "work freely and without fear of retaliation."
"This is a very disturbing development," she said in a statement, while the New York-based HRW charged that "more than twenty aid workers have been arbitrarily arrested, detained or threatened with arrest in the past six months in Darfur."
Arbour said targeting the humanitarian community "will not only do a disservice to the people of Darfur, it will draw attention away from the real criminals, those who continue to rape, kill and pillage with impunity".
MSF had done "nothing more than record these horrendous crimes and try to focus critically needed attention on them", she insisted.
"Rape and sexual violence are very real features of the life of the women of Darfur."
"This is the conclusion of our monitors, of the International Commission of Inquiry on Darfur and of all serious investigations into the unfolding human rights crisis in the region," the UN rights chief added.
"Its appalling that instead of arresting the people who have burned hundreds of villages and attacked thousands of women and girls," the Sudanese government is detaining aid workers," HRW Africa Director Peter Takirambudde said in a statement issued in London.
MSF stressed that the arrest of two senior coordinators in Sudan severely undermined its ability to deliver assistance in Darfur, where it is working in 29 locations with 180 expatriates and 3,000 Sudanese staff.
It has also been present in the rest of the country providing health care to millions of civilians for the past 20 years, often in cooperation with Sudanese health authorities.
Between 180,000 and 300,000 people have been killed in Darfur and at least 2.4 million others displaced since fighting broke out between local rebels and the pro-government militia in February 2003.