When using a custom theme (never happens with a clean magento2 installation, at least for me), if you put the verification code following the tutorial, which will tell you to place the verification code in the "head", it will not work for whatever reason. This is confirmed by inspecting the code after you follow the tutorial, as the verification code will not show up.
However, placing the html comment on the footer solved the problem for me in multiple websites with different templates.
In some cases the web server itself is filtering comments out which will make for an invalid verification as well as Piotr Kaminski also mentioned.
Hope this helps!