I would search for "topographic world map" rather than just "world map" to find something similar to the original Deluxe Paint image.
This one wouldn't be bad to use as a base. Resize to 320x200/256 and reduce the colours to 16 or 32, then manually touch it up, change the colours, add some textures or manual antialiasing, make it our own image.
