I didn't regear after lifting my XJ and going to 31" tyres. Mind you, this is with an AW4 and 3.55 gearing - which is liveable, but noticeably down on power compared to when it had the stock 28" tyres. Not to mention that fuel economy's gone from an average of around 15mpg to 12-13mpg; with what I've spent on fuel in the past few months I likely could've paid for gears.
Moral of the story: regear and go to 4.10s. 3.73s will be marginally better than 3.55s, but 3.93 is the equivalent to 3.55 if you're running 31" tyres (assuming you had 28" or thereabouts tyres stock), so you'll still be under-specced. I'm not aware of anyone who makes a 3.93 gearset for the XJ, so just go straight to 4.10s.