The behaviour you describe is correct for me. If you type a real sentence with 
several words you can see that it is the first white space which trigger 
autocorrection. So autocorrection comes first and start a new paragraph after. 
And "undo" replays the commands in reverse order.
To summarize for me it is not a bug.

For me its not logical - first should be done, what I do (paragraph end), then
what Oo does (AutoCorrect).
Because:
1. If I wouldn't press return, autocorrect would not start, so it cannot be done
before the paragraph end made by me!
2. It's the easiest way to undo autocorrection to press ctrl+z afterwards - but
with this strange sequence it's not (no more ↓) possible!
3. It was always like that in older versions (I think to remember)

Reassigned to ES.

I checked with "Ooo-dev 3.0.0 Beta Multilingual version German UI WIN XP:
[OOO300m2 (Build9343)]"  and can confirm some inconsistencies in the undo behaviour.

Example 1 (similar to report):
0. make sure that all checkboxes in autocorrect dialogue are checked
1. open new WRITER document
2. type an "a" and then a <space>
   <space> will insert a blank and additionally change "a" to "A"
3. click undo icon:
   result: Blank remains, "A" to "a"
   that's in accordance to meywer's needs

Example 2, verbatim as reported:
Here the cr-lf will not remain, behaviour differs from Example 1

I agree with meywer  that the undo stack seems to be inconsequent in example 2:
Autoccorrect works after initiation by <enter> (or <space>), and so the
autocorrect operation should be the latest one on the undo stack in both cases.

ES->AM: please have a look.