You need to include the yandex_123456d0a12.html file in your Service Package (cspkg) file for it to be deployed with your Web Role (in a Cloud Service).
Other options for validating Yandex are listed here: http://api.yandex.com/webmaster/doc/dg/reference/hosts-type.xml. If you don't want to redeploy the application it might be easier for you to add a TXT record (DNS level). This doesn't require you to redeploy the application.