5 - 30 minutos
After two years of being plugged in all day and discharging all night, my iPhone's battery wouldn't last more than a day or so off the charging cable.
If my iPhone 4 hadn't been at stake, I might have given up the replacement halfway through. The old battery was stuck fast inside the phone, and required rather forceful coaxing to remove. I was terrified that prying against the internal components would break them, but I was lucky and finally managed to get the old battery loose.
I don't think there's any good solution for a stuck battery - one just has to hope for the best, and keep working at it.