Flow My Tears, the Policeman Said by Philip K. Dick
This one is a strange one. I'm still trying to get my head around it. It's about a man who one day is famous and recognized by millions, to waking up the next morning and not existing, at least on paper and in all the data banks on Earth, and Mars. It makes him question what is real and not real. He also has to quickly get fake ident cards made so he doesn't get deported to a forced labour camp. He tries to confirm his existence and figure out what happened to him. Why doesn't anybody remember him? There are also police, pols, on his tail trying to figure out how this person could just erase themselves from all the data banks.