Не хочется переходить на личности, но аналогичное произошло года два назад в Express.Ru, собственноручно проверял три домена с очччень хорошими именами, уже после оплаты оказалось что они заняты. В принципе можно списать на случай, но нехорошие мысли все равно остались. Понятно, что проще всего проверять непосредственно у регистраторов, но раньше у экспресса была довольно удобная форма проверки множества доменов, которую впрочем уже давно написали под себя.
"Лечить" это лучше всего способом, прямой проверки домена у регистратора, хотя и в данном случае никто не застрахован, если регистрировать домен будет хостер. Поэтому либо нужно оплачивать домен самостоятельно, либо внимательнее выбирать хостера.