So I searched deeper because I knew that there is no "infinite" space for storing everyone's old passwords. After checking a couple of sites, I found this website which explains that Google keeps only last 100 passwords for every account. This means, if you are patient enough, you can reset your password. I said to myself "Challange accepted!" and with help of an Excel list, I changed my password 100 times. And voila! There I got my old password active again...