Yes, using Wish to wish someone dead is possible and is even presented as an example of a "custom wish" apart from the bulleted suggestions.
However, it is specifically listed as an example where the Wish might not work as the caster intends. Terms of fullfillment of wishes are up to the DM - the spell description states that wishing that a villain was dead might simply time-warp one to future after the villain's passing. The DM can also come up with other ways to make the target dead without effectively killing them, like turning them into a nonliving but equally powerful creature.
So, while the target actually dying is an outcome the DM can give, Wishing something was dead is not a reliable way to kill it.
Divine Intervention/Someone else's wish: Maybe?
Sadly, I think that's the best answer in this case.
While the use of a Cleric's Divine Intervention or even a Wish may overcome the penalty from the failed Wish, those are both going to ultimately DM decisions. I would agree that either should be sufficient, but if you put me in a corner, I'd say that Divine Intervention is more powerful than another Wish.
Technically, appropriate Divine Intervention is (PHB, 49):
The DM chooses the nature of the intervention; the effect of any cleric spell or cleric domain spell would be appropriate.
Wish is not a valid Cleric spell, nor do any other spells on that list have a means to undo the stress of Wish (although a very loose interpretation of Regenerate may). Allowing the Divine Intervention to relieve the stress would be completely up to the DM.
Using Wish itself would also have to be up to DM as you aren't replicating a known spell. However, you could wish for a certain card of the Deck of Many Things.
So...
But wait, there's more!
Another option that @Adam came up with is The Fates card from The Deck of Many Things is the only true RAW option. It can completely undo that casting of Wish. From the DMG, 164:
The Fates Reality's fabric unravels and spins anew, allowing you to avoid or erase one event as if it never happened. You can use the card's magic as soon as you draw the card, or any other time before you die.
This would effectively turn back time and undo that failed Wish casting that left you stressed.
Best Answer
Depends on how your DM is feeling
While the spell is named Wish, you are not actually posing your wish to any actual entity.
As you can see, you are not asking a divine entity for aid when you're casting wish, you're meddling with the very fabric of reality in an attempt to brute-force it into what you'd like to happen. It's not divine intervention.
Because it is not one of the default applications of Wish, you fall in the following paragraph:
Simply wishing "I wish Bob was alive again." might result in reality reshaping itself to erase the Lich from history, thus wiping out the event that killed Bob in the first place, or it might send you back into the past to a point where Bob was still alive, or it might just create a soulless clone of Bob, it depends entirely on your DM at that point.
Most likely the safest wish in this case would be to wish something along the likes of "I wish to speak to Bob's god, to make them aware of the fact that their soul has been destroyed by a Lich". It's in the god's best interest that Bob's soul is restored, so if there was any way of using wish to reliable revive Bob, this would likely be it.