s/when moving a protection page/when moving a protected page/

You should find a protect log entry under the target like this (at least in 1.20):

HH:MM, DD MM YYYY User (talk | contribs) moved protection settings from "A" to "B" (Reason)

clearly wrong behavior.
logically, the logs are just another part of the page history, "meta-history" if you will.

the same logic that's used vis a vis history, should apply to logs.
when you move a page, the "history" remains with the move target, and the move source starts its life with (almost) clean slate, containng only the move operation as "page was created".
it makes no sense that the historical logs remain with the move source, and the target logs begins from 0 at the date of the move (optionally with "move protection" or somesuch, if the target was protected at the point of the move).

for instance, if the page was protected/unprotected in the past, let's say because of repeated vandalizm, how is it logical that the traces of vandalizm (i.e., page history) are with one page, and the traces of pretection/protection removal (i.e. logs) remain with a different page?

there is no other way to describe this behavior than "bug".

fuhghettaboutit wrote:

I just saw this in action. A user at the en.wikipedia help desk was confused because they could not move a page. I don't know if they actually checked the logs, but in order to tell the user definitively that the page was move-protected, as I immediately suspected, I had the trace back the title through two generations of moves to find the protection log entry for the original title.

The fact that there were two generations of moves here shows how problematic this could be. There are pages that have been moved many more times than that and there are many people who are not conversant enough to trace back a page to the original entry, though they may have a very good reason for wanting to see not just the automatic log entry but any tailored edit summary that accompanied it.