במזרח ירושלים מתגוררים כיום למעלה מ-300 אלף פלסטינים. רובם ככולם אינם אזרחי המדינה אלא תושבי קבע, אשר רשאים להתאזרח על פי הוראות חוק האזרחות. ממילא, בהקשרים רבים התושבות חשובה יותר מאשר אזרחות: למדינה יש חובה להבטיח ולהגן על זכויות אזרחיות של כל מי שבשטחה ולא רק של אזרחיה, וחובותיה בתחום הכלכלי-חברתי, כמו הזכות לחינוך ולביטחון סוציאלי, מותנות בתושבות, לא באזרחות. אלא שתושבותם של הפלסטינים במזרח ירושלים אינה בטוחה, ולכן הם אינם נהנים מביטחון בזכויותיהם.
מעמדם של הפלסטינים תושבי מזרח ירושלים נקבע באופן פורמלי לראשונה בפרשת עואד ב-1989. מובארק עואד נולד במזרח ירושלים ב-1943, ונרשם במרשם האוכלוסין כתושב העיר ב-1967. ב-1970 נסע לארצות הברית והשתקע שם. ב-1987 הוא ביקש לחזור לירושלים אך משרד הפנים סירב לכך, בטענה שתושבותו של עואד פקעה. בעתירה של עואד לבג"ץ נפסק שניתן שמעמדם של תושבי מזרח ירושלים הפלסטינים הוא כשל מי שקיבלו רישיון לישיבת קבע. תושבות קבע מותנית במגורים בפועל במדינה, ומי שהשתקע במדינה אחרת, כפי שעשה עואד, תושבותו פוקעת.
ההתייחסות לתושבי העיר הפלסטינים כתושבי קבע רגילים היא בעייתית באופן עקרוני ובאופן מעשי. הבעיה העקרונית היא שמוסד תושבות הקבע מניח שתושב הקבע מחזיק באזרחות של מדינה אחרת, שאליה הוא יכול לחזור ומחויבת לקבלו. המוסד הזה לא מתאים לאנשים שאין להם אזרחות, ושעם אובדן התושבות הם מאבדים כל מעמד שהוא. זהו בדיוק מצבם של תושבי מזרח ירושלים הפלסטינים: הם אינם אזרחי מדינה אחרת שיכולה לקבלם. יהיו מי שירצו להציע להם "ללכת לרשות הפלסטינית", אולם ישראל אינה יכולה לטעון שהגדה המערבית היא יעד להגירה ובה בעת להתנגד לכך שהגדה תרכוש מעמד מדיני מלא. הצעה זו גם מזמינה את האפשרות שאם יהודי תושב אירופה ילין על פגיעה בזכויותיו, הרשויות תשבנה לו "שילך לישראל" במקום להגן על זכויותיו.
המדיניות של משרד הפנים מעוררת גם בעיה מעשית: במצב רגיל, תושבות פוקעת כאשר אדם שיצא את המדינה מבקש להיכנס אליה לאחר למעלה משבע שנים, אם מתברר שהוא השתקע בינתיים במדינה אחרת. במזרח ירושלים המצב הוא הפוך: השאלה אינה אם אדם עזב את העיר, אלא אם הוא יכול להוכיח שהוא נמצא בה. בכל פעם שתושב מזרח ירושלים בא במגע עם הרשויות, הוא נדרש להוכיח שירושלים היא עדיין מרכז חייו. לא די בכך שהוא רשום במרשם האוכלוסין ושלא יצא בגבול.
דרישת ההוכחה המתמדת של נוכחות בעיר משרתת את שאיפתה המוצהרת של ישראל מאז 1967, לשמור על רוב יהודי בעיר. במהלך השנים נעשה שימוש במגוון כלים להשגת יעד זה – מעידוד הגירה יהודית לעיר, דרך הטבות לפלסטינים העוברים לגדה המערבית ועד מגבלות בנייה בשכונות הפלסטיניות במזרח ירושלים. הדרישה להוכחה מתמדת של מרכז חיים מאפשרת לצמצם את האוכלוסייה הפלסטינית בעיר, לפחות באופן פורמלי. למשל, על פי נתוני משרד הפנים פקעה ב-2016 תושבותם של 94 אנשים. תושבותם של שניים בלבד פקעה בעודם מחוץ לישראל. כלומר, 92 אנשים איבדו תושבות בעודם בישראל.
דרישת ההוכחה המתמדת לא הייתה אתגר לולא הקושי המעשי להוכיח מרכז חיים. ראשית, בהיעדר היתרי בנייה ורישום מקרקעין במזרח העיר לא ניתן להציג הוכחות תושבות מקובלות, כמו חשבונות ארנונה, חשמל או מים. שנית, מגורים בעיר הם תנאי הכרחי (אך לא מספיק) להיותה "מרכז חיים", ורבים מתושבי העיר הפלסטינים נאלצים לעזוב אותה אל מעבר לגבולותיה המוניציפליים נוכח הקושי הגדל להתגורר בתוכם, קושי שהתעצם מאז בניית גדר ההפרדה. ה"עזיבה" היא לעיתים מעבר של מאות מטרים בלבד, באותה שכונה, ובכל זאת למעבר יש השלכות הרות גורל.
במארס 2017 התקבלה בבית המשפט העליון החלטה אשר יש הרואים בה נקודת מפנה. עניינה בקשתו של אכרם עבד אלחאק להשבת מעמדו כתושב. אלחאק נולד במזרח ירושלים ב-1959, ב-1971 היגר עם הוריו לארצות הברית, וב-1989 חזר לירושלים. כמו בעניינו של עואד, משרד הפנים סירב לחדש את תושבותו. במהלך השנים ביקר עבד אלחאק בירושלים לתקופות ארוכות, נישא פעמיים, ושתי נשותיו וילדיהם גרים בירושלים. מאז 2007 הוא חי בירושלים באופן בלתי חוקי, וב-2014 הוא עתר להשבת התושבות שלו.
הבקשה סורבה. בהחלטה בערעור ב-2017 ציין השופט מזוז באמרת אגב, שעל הרשויות להתחשב "במצבם הייחודי של תושבי מז' ירושלים כתושבים ילידים – להבדיל ממי שקנו זכות לישיבת קבע מכוח רישיון לאחר הגירה לישראל". החלטה זו נראית ממתנת את הלכת עואד, אך עדיין אין זו הלכה מחייבת. בית המשפט קבע שיש לתת לעבד אל-חאק רשיון ישיבה (ארעי, בשלב ראשון), אך לא על בסיס עקרוני אלא נוכח הנסיבות הספציפיות. יתכן שהפרשה הזו מבשרת שינוי, אך היא איננה מהפכה.
המצב במזרח ירושלים אינו עניין של סיכום טורים מספריים בתחתית דפי מרשם האוכלוסין. בין אם רואים בפלסטינים במזרח ירושלים תושבים הזכאים לטיפול הרשויות, בין אם רואים בהם נטל בטחוני וכלכלי, מחיקה ממרשם האוכלוסין לא מאיינת אנשים, אלא רק מורידה אותם אל מתחת לראדאר של הרשויות. מצב זה אינו מיטיב עם אף אחד מהנוגעים בדבר.
