Wurden diese Fotos überhaupt mit dem iPhone gemacht? Sonst würde ich eher vermuten, dass die in der Cloud liegen, aber aufgrund der nicht mehr stattfindenden Synchronisation aufgrund des überschrittenen Limits nicht mehr abgerufen werden. Ich würde an erster Stelle mal das Kapazitätsproblem beheben, kann man ja auch aufräumen anstatt zu bezahlen, und sobald der Sync wieder läuft dürften auch alle Elemente wieder da sein.
Wieviele Fotos wirklich jetzt am iPhone liegen, siehst du in den generellen Einstellungen bei den Details über dieses iPhone, dort zählt es die Anzahl an Fotos, Musiktracks...