How do top graduate programs in mathematics verify the validity of an enrolee's undergraduate degree from abroad? E.g. IUM in Russia
IUM (quite purposefully) distants itself from the "officially recognised" education and relies on informal recognition in a sub-group of well-established mathematicians. As an IUM graduate, you most likely will be recognised as an outstanding candidate for your ability to do maths. You will also have recommendations of internationally renowned mathematicians. Many academics will feel themselves very reassured hiring someone with IUM credentials. 

However, universities do not consist of academic only, and HR departments may have their views on the process, too. It is fair to say that even the best professors sometimes have only limited influence on HR when it comes to formalities. And of course, the list of recognised qualifications is one of such things. 

Unfortunately, there are no universal rules which HR departments apply. It is likely that for a particular unusual situation like the one you described, the decision will be made ad hoc by someone in HR department; once it is made, it is unlikely they will go back on it.

That is why many of IUM graduates prefer also to get themselves a degree from officially recognised university. Even if it does not give them the level of education compared with IUM, the official degree always works well to pacify the HR departments, while academics will always look at IUM degrees on your CV as something really outstanding.