Edited title to fit in the box.  Minimal reproducer, which can become a test.  File as follows, where '|' represent the cursor, not the character.

a
a|
a

Cntl-H, enter search for 'a', replace with 'b', check 'up', uncheck 'wrap', click Replace All.  Result matches what you said.

a
b
b

Thanks for the report. This is definitely a bug.  In the future, try to post a minimal example, such as the above, as well as a description.   Whether I backport a fix depends on how easy it would be.