Kalata
Out of the Silent Planet
Actually, the artwork you talk about is the one that is included in the booklet (see here) - the more detailed one is included in the vinyl.The inside cover has some fantastic detail but I think less (i.e. the glowing Eddie in the middle plus two Maidenheads totems) would be more better.
The obvious choice is Melvyn Grant, who is also a great artist and they worked with him for 3 album covers. Or they can choose someone they haven't worked with before.I wish they'll find a worthy replacement for Mark or better, they come to terms until the next one.
I think Akirant Illustration would be a good choice - they worked with him for a cover of a live album and for a few tour posters and he has done some amazing additional artworks for Senjutsu. Great artist too.