722.
My apologies, Super Luigi. My life has been quite busy and I wanted to give you all some food for thought..
Boy do I love a good thought experiment. I'm not sure the order of choosing the numbers matters... just as long as you account for the numbers 1-100. If I have done my counting correctly, I believe there are only 18 palindromes from 1-100 (1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99). Cyclone, I agree with your answer.
For the number of palindromes in 5000, that is a very complex question (adding an extra tens place would greatly increase the number of palindromes). I would need a bit more time to answer that, but I'm assuming it would turn out to be hundreds of palindromes.