Sorry to hear about losing your photos. If you format your card, you will lose everything on it. If you've taken more pictures since you've tried to recover the photos off the card, then you might've lost all of your images. Another thing is that if it was taking longer than usual, your card may be corrupt. Cards have a write/re-write lifecycle, and just like any piece of hardware, it will eventually die.
Before I'd format the card, I'd do the following: Run some recovery software, see what it comes up with. Immediatley after running the recovery software, run the same program again. It might get something that it missed the first time around. After running it the second time, I'd run a different recovery program, two times, one right after the other just like you did the first one. If it comes up empty handed after using both programs, then I'd say (sadly) that you're images are lost. You always have the option of sending the card to a company to have them try to recover the photos, but that's extremely expensive (hundreds of dollars!).
If you can't recover the images, then I'd format the card. I strongly recomend letting the camera format the card, as it's good practice to let the equipment format the media.
After formating it, I'd check it for errors, and see if it needs to be defragged. Remember, a card is just a small memory device, much like ram (or a hdd minus the moving parts), it's a storage device. When you write, re-write, copy to and from and delete information (pictures) to it, it's bound to need "maintanace".
If you are unable to format the card, or the camera says it's corrupt, or partially corrupt, then try having windows format it. If that fails, you can try to wipe it clean using other softer (will explain if you get to this point), then after it's been wiped, you can try reformatting again. If you still can't reformat it, or it comes up saying it's corrupt or partially corrupt, I'd get rid of the card and purchase a new one, as the card is on it's last leg, and will do nothing but cause heartache and gray hair!
Hope this helps, and please post back letting us know how you make out! Good luck!