Should I do the factory reset? If yes, what will I lose? My HTC Desire S is working fine when I don't put my micro SD card in it (this card was free with the phone). But the phone keeps restarting every few minutes if I keep the memory card in it. By that, I could say that the phone is fine, but the issue can be either with the memory card or the phone not supporting memory card anymore. The phone and memory card worked completely fine for 8 months.

The thing is, if the same memory card is inserted in any other mobile, be it an Android or any other smartphone, that phone will not restart and the data is completely readable too. So, the memory card is fine. When I insert some other memory card on my phone, then my phone does not restart too. So that means the issue is with my phone &amp; that particular memory card combo.  

I am ready to uninstall each and every app from my phone, but will that solve my problem? Should I perform the factory reset? Will it solve my issue? What will I lose if will do the factory reset? Like: contacts, SMS, call logs, APN settings, etc. Any free software to backup all these?

But maybe I am going in the wrong direction. Maybe there is some easy way to get the phone and memory card working.
Doing a factory reset will not modify the SD card in any way. Only the data on the phone will be deleted. Contacts that are set up to sync with your Google account will restore, but everything else will be gone. 

If you have applications installed on the SD card, I would start there. Uninstall them, or move them back to the device storage. You say that it only crashes when it is in your phone, and not any other Android phone. This would make me think there is probably an app installed on the SD card for your phone. You also said that it doesn't reboot when a different card is in your phone, again leading me to believe that there could be an app that is installed to the SD card that is causing problems.

If you think there is something in your data that is causing the issue, then backing up the data with Titanium Backup will just restore any "issue" that there is. 

If you think the problem is with the data on the SD card, then you can format it under storage in settings.

I would also consider the SD card itself could have issues. The SD cards that come with the devices are very cheap cards and usually one of the slower class type of SD card. I have had a few of them last only a couple of months before. I suggest getting a better SD card, one that is at least a class 6. If you have a slower class card, this could also potentially cause issues with some applications.