From emacs -Q:

;; We do a query-replace to remove NUL characters and replace them by
;; an empty string:
 M-% [query-replace]
 C-q [quoted-insert]
 0 <return> <return> [exit-minibuffer]
 <return> [exit-minibuffer]
;; now we try to do it again, by relying on the history
 M-% [query-replace]
 <up> [previous-line-or-history-element]
 <return> [exit-minibuffer]
;; At this point, emacs asks what to replace "two NUL chars" with,
;; instead of removing NULs like the previous query-replace did.

In GNU Emacs 25.0.50.1 (i686-pc-linux-gnu, X toolkit, Xaw scroll bars)
 of 2015-05-07 on Aurora
Windowing system distributor `The X.Org Foundation', version 11.0.11501000
System Description:	Ubuntu 14.04.2 LTS

I suggest the following changes :