Should unreadability or sloppiness of students' work be reflected in their evaluation?

I think the most important part of your post is in your comment

Or for example grant agencies simply reject proposals that fail even slightly given formal criteria.

If a student isn't corrected for sloppy work while in school, when will he or she improve? The question really boils down to

How best can we as instructors give guidance to students so that they will succeed in the future?

Evaluations in an educational setting can serve many purposes, but fundamentally they should be used as a tool to help students succeed. Obviously, you have to be careful because a poor grade on a transcript can have long-term ramifications, but ignoring sloppy or unreadable work by trying to see through it is doing a disservice to the student on a particularly key issue: communication of an idea is as important as the idea itself.

To answer your questions:

1. Should the evaluation include evaluation of readability, proper structure etc...?

Absolutely. To ignore this would be bad pedagogy. Determining how to relate this to the student without causing a misunderstanding about the idea itself is the difficult part. Encouragement or direction to seek out writing help is a good idea, as is having students re-write or re-submit work that is sloppy. Hopefully the work improves throughout the course; being picky at the beginning of a course can set a good standard for the rest of the course.

2. Should such deficiencies be also reflected in the grade? If so, how much? Would it be acceptable to even fail a work just because it's completely unreadable?

The answer to this ties directly back into the first question. I would suggest letting students re-write or submit material without penalty (or with minimal penalty) early on in a course, with the understanding that they must improve by the end. If your only assessment is a final project, consider allowing a re-write with an incomplete grade. But, if that is your policy, I'd strongly suggest providing a time for draft review well before the final project is due in order to minimize the need for this route. As always, I would also spell out in a syllabus your policy and the fact that presentation is a part of the course, and I would also discuss this on the first day of class (with examples of past work that is sloppy!).

You've posed a hard question, but an extremely important one. I probably suggest rejecting 30% of the papers I review for conferences simply because they are unreadable. Most of the time I don't even get to the idea behind the work before I realize that it doesn't matter what the idea is because it is too poorly written (and this ends up in the review). I want more papers that are well presented, because I'm certain some of the papers I give poor reviews to because of this problem have great ideas behind them! Teachers that encourage students to improve their writing and presentation are necessary for this to occur.