Nightmares and frustrations with students' sloppy homework
It could simply be students doing the minimum in order to get by. The solution is to raise the minimum. To do that, start denying points for non-compliance.

As Suresh wrote in his comment, electronic submission might be appropriate. In my classes I require that whatever students submit be word-processed written in a specific font. If the students do not follow the instructions then I treat them as if they never submitted at all. As you can imagine, seeing this one time in class gets everyone to pay attention.

Basically, eliminate hand-writing if you can. Some students simply have very poor penmanship so it's best to structure things so they can use a computer. Ideally, save the paper and submit electronically.

If you cannot eliminate hand writing them make it clear that if you cannot read (or understand) what they wrote then their score will reflect that. I have issues with some students writing in English (not their first language) and I make it very clear that I'm not here to judge their English but if I cannot understand their intention without guessing, I will simply mark it as gibberish.