What is the source of the old Minhag of removing ones shoes at the Kotel and why did the practice fall into disuse?

I did not hear of that old custom but that does not mean it did not exist. I reckon it comes from the Halacha that one is not allowed to enter the temple mount with shoes as a sign of awe (Rambam Beit Habchira 7; 2), and the reason it is not common practice is because it is not temple mount but only the Kotel.