I can reproduce the error with another Natural Earth image http://naciscdn.org/naturalearth/10m/raster/NE2_LR_LC.zip and GDAL version 2.0-dev. Write a mail into gdal-dev mailing list. I believe that the issue is real and you can file next a ticket into GDAL bug tracker.
I also verified that problem is not caused by the lanczos resampling but "-r average" produces the same artifact.
As mentioned in an answer by Andre Joost, the issue can be fixed by adding parameter
-wo SAMPLE_STEPS=1000 into the gdalwarp command. The whole explanation from gdal-devA is worth including here:
Adding -wo SAMPLE_STEPS=1000 fixes it (1000 is experimentally found.
100 was almost perfect, and then I just tried 1000). The default is
The issue here is that the warper process by rectangular regions of
the target dataset and then tries to find the rectangular region of
the source dataset that matches. In the corners, which are full of
target pixels without any valid source pixels, the default sampling
logic doesn't manage to identify properly the source pixel region due
to a too low sampling step.
The higher SAMPLE_STEPS, the slower the warping is (in theory,
practical speed might depend on situations)
Playing with -wm has possibly an influence on the result too, but that
might be even more magic to play with that.