In what a report by B'Tselem, the Israeli human-rights group, calls "a policy of quiet deportation of East Jerusalem's Palestinian residents", hundreds and perhaps thousands of people have already been forced to leave. Western consular officials in Jerusalem fear that as many as 120,000 out of 170,000, two thirds of the Palestinian population, could lose their right to live in the city.
So far the regulations have been mainly enforced when a Palestinian needs to renew an identity card, but the Israeli Interior Ministry says that between June and August all identity cards must be renewed.
As a result of the policy, which started early last year but which has been more harshly enforced since Benjamin Netanyahu became Prime Minister, many Palestinians born in Jerusalem have stopped registering their children. Su'ad Nimr, 32, who is the mother of three children, said: "I was born and raised in Jerusalem as was my husband. Four months ago they took away our identity cards. Now my husband cannot leave the house. We live in fear that he will be imprisoned."
Eliahu Abrams, a civil-rights lawyer, said: "It is a true crisis in human rights: Israel is forcibly getting rid of Palestinians not by pulling them out by their hair, but by quiet, slow, sophisticated deportation." The essence of the new policy is to force all Palestinians to give documentary proof - often twelve different documents - showing that they have always lived in the city.
Olga Matri Hana Yoaqim, 63, who has seven children, was born in Bethlehem but has lived in the city with her husband since 1952. "In September 1995 I went to replace my identity card at the Interior Ministry office in East Jerusalem," she said. The clerk cut up her old card and told her to come back in two weeks. When Mrs Yoaqim returned "the clerks told me: "You don't have an identity card. Go to the West Bank".
Her husband went back to the ministry 20 times but was refused. Mrs Yoaqim said: "I suffer from diabetes and have kidney problems. When I go to a clinic or hospital, they want to see my identity card. Because I have none, I can't receive treatment."
The Interior Ministry denies that it has a new policy, but says it is merely enforcing old regulations. Responding to the allegation that it has embarked on a policy of deportation, Tova Ellinson, the ministry spokesperson, said: "When permanent residents sever their connection with Israel - maintain their centre of life in another location... - their free choice causes the expiration of their permanent residency."
In fact, it is only recently that Palestinians who live in a Jerusalem suburb such as Ram or Abu Dhis have found that their "centre of life" has moved from the city as much as if they had moved to Dundee. B'Tselem, in its report, The Quiet Deportation: Revocation of Residency of East Jerusalem Palestinians, says: "Some 18 months ago, the Interior Ministry began to revoke the residency status of persons who moved outside the municipal borders of Jerusalem."
The change was retroactive and introduced without notice so it is only now that Palestinians are discovering if they have the right to live in the city where they were born.