But neither the Danish government nor the newspaper are backing down.
The ambassadors of 11 Muslim countries called on Anders Fogh Rasmussen, the prime minister, to take "necessary steps" against the "defamation of Islam".
But Mr Rasmussen, the head of a centre-Right minority coalition dependent for its survival on support from an anti-foreigner party, called the cartoons a "necessary provocation" and refused to act.
"I will never accept that respect for a religious stance leads to the curtailment of criticism, humour and satire in the press," he said.
The Danish debate over how to integrate Muslims has raged for years, with nursery school menus and women-only opening hours for swimming pools particular battlegrounds. But the cartoons satirising the Prophet have injected a dangerous new element into the controversy.
"This is a pubescent demonstration of freedom of expression that consciously and totally without reason has trampled over the feelings of many people," said Uffe Ellemann Jensen, a former foreign minister and member of Mr Rasmussen's party.
Carsten Juste, the editor of Jyllands-Posten, spurned demands that he apologise, saying he "would not dream" of saying sorry.