TL;DR: Yes, but it's extremely rare and I could only find one example.
Has there ever been a medically verified case of someone having a big part of their body paralyzed for years, due to a car accident or similar event, who eventually recovered the normal functioning of their paralyzed body part?
It's very rare but I did find one example:
The patient, a 58-year-old male, endured vertebral fractures at
cervical levels C3–C6 in a motor vehicle accident at the age of 22.
The patient did not have any respiratory problem and his stay in the
ICU was limited to 5 days. Following the injury, the patient underwent
manual motor testing of lower and upper body muscles groups as well as
sensory testing. The motor testing involved examination of flexion and
extension of upper body (shoulder, elbow, and wrist), and lower body
joints (hip, knee, and ankle), and sensory testing involved
examination of sensation to pinprick and light touch on both hands and
feet. Initially, the patient had no motor or sensory function below
the level of injury. Motor and sensory function at the sacral level
was also absent, which was tested during the bladder evacuation and
catheter placement procedure. This injury is equivalent to an ASIA A
(ASIA: American Spinal Injury Association), or a “complete” injury,
according to today's ASIA impairment scale (AIS) (Maynard et al.,
1997), which did not exist at the time of the patient's injury.
The case history goes on to describe his recovery:
He experienced slow and progressive neurological recovery that
continued for 17 years after the injury. The first neurological
recovery, movement of the left big toe (a grade 1 motor function),
occurred 6 weeks after the injury. The first recovery of sensation
occurred 6 months after the injury in the form of a painful
dysesthetic sensation in the pelvis. Eleven months after the injury,
the patient was able to perform complex upper body motor functions
such as sitting up without assistance. Complex lower body motor
functions such as ability to walk unassisted were recovered 15 months
after the injury. Concomitantly, the patient recovered autonomic
nervous system functions (i.e., a high degree of bladder and bowel
functions were recovered up to 64 months after the injury) although
many remain abnormal (Table (Table1).1). Currently, his injury is
categorized as ASIA D. His latest AIS evaluation (Figure (Figure1)1)
showed that he has regained 94% of motor function in the upper body
and 100% in the lower body. The patient manifests incomplete and
asymmetric motor recovery in his hands—i.e., his left hand is more
functional then the right one. He has also regained 23% of sensory
function in the upper body (above the level of T7), but only 10% in
the lower body.
You then ask:
If there are such records, what are the most plausible explanations?
This is purely my opinion but I would say normal regrowth of neurons explains it. The fact that the first hint of recovery occurred after six weeks and then it took another 17 years for him to achieve the degree of partial recovery he ended up with is a strong argument for entirely natural processes. Neurons can reconnect, but it's known to be a very slow process.