Great question! I also have the same problem (don't we all?) in absolutely any class I teach. One additional idea that I've recently came to is the following. Our students don't distinguish between solving a problem and writing your solution. Solving can naturally be messy, because you need to think and figure out how to do solve the problem. Of course, even that idea is quite novel to many students, because mostly they view their math classes as training in following the given step-by-step samples. But back to solving: after you figure out how to solve the problem, you need to write a clean narrative for someone, such as your instructor or grader, who will read it. But our students don't realize that: their idea of working on a math problem is to immediately start writing all over the place, scratching and crossing and correcting as necessary hoping to get to the answer, and they believe that that's what expected as their submission.
So I recently started telling my students that for any work they do, be it homeworks, quizzes, or even in-class tests, they need two stacks of paper: some scratch paper where they figure out a solution, and one clean paper (for in-class tests, it's the test paper itself where space is provided) for writing a clean version of the solution. I can't say that it actually solved their messy writing issue completely, but quite a few students followed my advice and actually started submitting nicely written works!
Besides that, I agree with the excellent answers above. I use some grading penalty too, but not always — depends on the messiness of the paper, difficulty of material, etc.