strange behaviour in keyboard macro

[Héctor Lahoz]

I saved a keyboard macro like this:

<<search-forward>>      ;; search-forward
Priority:               ;; self-insert-command * 9
SPC                     ;; self-insert-command
required                ;; self-insert-command * 8
RET                     ;; newline
<<backward-paragraph>>  ;; backward-paragraph
C-n                     ;; next-line
<<search-forward>>      ;; search-forward
:                       ;; self-insert-command
SPC                     ;; self-insert-command
RET                     ;; newline

When I execute it sometimes it does what I mean and the cursor ends on the 
right line.
But sometimes it ends (erroneously) on the following line. For example (I added 
numbers
for reference):

1: Package: mypkg
2: xxxxxxxxxxxxxx
3:  xxxxxxxxxxxxxx
4: Priority: normal
5: 
6: Package: mypkg2
7: xxxxxxxxxxxxxx
8: Priority: required

backward-paragraph should set the cursor at line 5 (blank line) so
cursor should end up at line 6.

At first it seemed random. Then I tried to find a pattern and found
out that it has something to do with text scrolling. When I repeat the
macro starting at a distant point (like half the window size) I manage
to get alternating results, that is, with one execution it ends at
line 6 and with the next execution (reseting the start position) it
ends at line 7.

Emacs version 24.4.1. Fundamental mode.
Is this a bug? I think with emacs 23 it worked fine.