MHEG isn't specifically to do with PVRs.
Consider it as a bit like a TV version of HTML, the code that's used to create web pages. MHEG is used to provide the interactive features - the 'red button' stuff. It's what allows receivers to jump to a different video stream, like the News24 interactive stuff, the different tennis courts during Wimbledon, the Spooks Interactive game and so on.
So, it's not essential by any means - and in many other countries they use something called MHP instead, hence the questions about whether or not boxes originally sold elsewhere will have MHEG - but if it's there, it's handy, and it allows you to make full use of the interactive facilities provided by the various broadcasters.
It's something I'd look for in a box, though I'm not sure how often I really would use it; just like analogue teletext, it tends to be something that's handy to have around, even if you do just use it once in a blue moon to check the news headlines, or look up a flight arrival.
Nigel.