Pokud tam bylo telefonní číslo zadané bez +420, nešachovalo se v tom účtu se státem? Píšete, že Google píše, že se změnilo telefonní číslo, ale vy žádnou změnu nevidíte – tak jestli se nezměnil ten stát, který Google přidává před národní telefonní číslo.
Akorát teda pokud to tak bylo, asi to telefonní číslo v jiném státě stejně neseženete...
Nemáte k tomu účtu přístup na nějakém zařízení s Androidem, kde byste aktivoval ověřování pomocí notifikací (,,Výzva od Googlu")?
Obecně bych doporučoval zrovna o Google účet trochu pečovat (zejména pokud je na to navázán GMail a další služby), tj. průběžně, jestli nepožaduje posílit zabezpečení, mít tam ověřené telefonní číslo, vygenerované záložní kódy... Jak vidíte, řešit to zpětně je dost problematické a pokud tam jako jediný způsob, jak se prokázat, máte to telefonní číslo, a přes to se to nepodaří ověřit, pak o ten účet pravděpodobně přijdete.