I am quite sure that the first painting constitutes a criminal copyright infringement.
Difficult to say -- "satirical intent" and "parody" are often (but NOT always) a defense against copyright infringement, and I think it's clear that both of the Birk paintings have satirical intent. For example, I would assume that in Liberation of Baghdad, he intended to compare the Bush administration's portrayal of the war with [ominous music] SOVIET PROPAGANDA!!!

On the other hand, "parody" by nature assumes that the audience is generally familiar with the source being copied, and I doubt that the Volkov painting of Minsk is known to most Americans. So it would be difficult to prove unlawful "plagiarism" of Dali's The Persistence of Memory...



...because the work is universally known and every viewer immediately understands that the artist does not intend to present his parody as a completely original work. But the "average American viewer" of Birk's work would not realize that Liberation of Baghdad is "quoting" heavily from someone else's work. (However, if Birk presented a framed print of Volkov's original side-by-side with his own painting, that might be a successful defense against plagiarism.)

On the third hand, IANAL, so my analysis might be totally wrong.