There are many reasons for handwriting problems, and many of these reasons may not be remedied with mathematics education methods and approaches. For example, Asperger's Syndrome has been associated with difficulty in handwriting, and it is possible that you would not be aware of this student being on the spectrum. While not a disability, Asperger's demonstrates that there is a possibility we will see students with unbalanced levels of ability. It's especially surprising to see a student exhibit mathematical understanding, and then struggle working a problem because of writing.
If the problem is simply that the student just has not had enough practice with handwriting and has not had a chance to become good at it, the answer will clearly be: practice. Or help from someone who specializes in writing (not a mathematics educator in either case). However, the older the student, the less likely it would seem that lack of practice would be the issue.
If the problem is something along the lines of what I suggested above (or many similar issues outside of a lack of practice), it is possible that time pressure is a contributing factor. As noted in studies on Asperger's-related handwriting issues, speed is a factor in student writing, and speed demands increase as students progress in age. So, one possible remedy is to recognize that writing is going to be slower than what you would expect, and accommodate that by changing expectations and allowing more time. Stress clarity, not speed.
To address the school problem, if it actually has been a problem for this student, students can often get accommodations to allow for mismatched skill levels that would interfere with assessment. That may only occur with a diagnosis; the school administration can guide you here. Local ways of doing things differ (all over the world, of course).
We might also more generally talk about the problems that ELL (English Language Learners) have with mathematics education. It's another case in which a skill outside of the mathematics education realm may interfere with either learning or assessment. And there are many people concerned with this problem. If we look at some of what researchers consider there, what can we take away? One thing is that, as math educators, our job is not necessarily to make all students do things the same way. Developing mathematical skills and knowledge may mean working with a student's strengths (like the ability to discuss mathematics) rather than a focus on deficits (which you may not be able to address in math tutoring or classrooms).
A short answer here: workarounds. Possibly more structure in the writing and less actual writing.
What form would that structure take? You specifically mention a difficulty going back and interpreting handwriting that was done 30 seconds ago. Assuming the student is doing fine while writing, what may help here is the ability to recognize the higher-value portion of the writing and pay special attention to that so that the student can come back later if needed. For example, an important result, or a simplified expression that will be of use later? Re-write that patiently and put a box around it. This may be more effective than just having the student slow down everywhere -- just learn to recognize what part of the writing is important, slow down there, and put a box around it.
Aside from the research I referenced in the links, I personally have struggled with handwriting issues (not diagnosed with anything in particular) and organizational problems; this is how I deal with them. Focusing on what's important, taking more time and care with the most important things, and adopting some kind of structure that supports my efforts.
While we may not be able to remedy handwriting problems in math education, we can address the problem somewhat by understanding how handwriting, and the particular abilities of a student, interact with their mathematics activity. We can accommodate, or we can provide supports that help them to use their ability most effectively. And we can teach them skills and habits so that they can support themselves in the future.