Addend on Lithium batteries (the most common kind used for laptopts).
The discharge "completely and recharge" advice applies to NiCad and some other kinds of batteries, but is NOT a recommended procedure for Lithiums. Discharging below the point where the voltage starts to drop will shorten the life of the battery, and full discharge may make one unrecoverable. Li batteryies are shipped charged, on the assumption that they'll arrive and be placed in use before fully discharged, and laptops in particular will normally turn off once the battery voltage starts to decrease, to prevent complete discharge.
One packager, probably a manufacturer, states that all Li batteries should include several safety features. I'm not sure whether he is referring to "batteries" in the technically correct sense of multi-cell packages, and whether this also applies to single cells (commonly but improperly called "batteries.")
In packaged Li batteries for a computer, to prevent hazards to users, all batteries should have an internal fuze that opens if rated input or output current is exceeded. This permanently disconnects the cells from the output terminals and renders the battery "dead."
In packaged Li batteries for a computer, to limit the hazard from case rupture, the same or a separate fuze will permanently disconnect the cells from the output if the battery temperature exceeds a temperature set by the manufacturer, usually about 100 C.
In some areas, one may find "battery shops" that advertise the ability to rebuild "packaged batteries," including the kind used in computers. They can open up the case, match the type, size, and number of cells with replacement cells, and hence produce "rebuilt" batteries at prices they claim are significantly cheaper than getting manufacturer's replacement batteries. I have no experience with these kind, but some people I've known have said the ones here did a good job on replacements for their portable hand tools.
Most of the batteries people claim to have had rebuilt, though, are "screwed together" cases, so breaking out a seal over the screws allows easy disassembly. Most computer batteries I've seen have welded, molded, or glued-together cases, so they would have to actually "break" the case to get into it. Inquiry with a shop of this kind might be worthwhile, but a liberal dose of "good judgement" should be applied to their claims before handing over your cash.