I am right handed, and my handwriting is barely legible (somehow, though, my teachers can apparently read it). At least my grammar, syntax, and conventions are pretty much perfect though.
I think much of the reason I write bad is because most of the assignments given in school that have free response are completely starightforward questions that require absolutely no thought to answer. I don't care about those questions and just bullshit it, in both handwriting and the answer itself.
On free response questions that require more thought, I generally always think of only a few things and then immediately begin writing. But while writing, I constantly come up with even more things to write about, so I write as fast as possible so I won't forget what I want to write about, and that speed causes my writing to suck.
Either that, or my handwriting just naturally sucks. Those are the only two options I see.