Domain was redirected before it expired

Here is a situation:

After domain registration I discovered that it was previously used. Nothing strange about it and I'm sure it happens all the time. However, before it expired, I think it was "officially" redirected to a different site.

And now, if you search for my domain, that other site still comes up. Even if you look specifically for content from my site using "site:" tag in google like this site:mynewdomain.com

Did anyone experienced anything similar? I know it takes time to index or re-index a site, but I did followed all good practiced, created content, sitemaps etc. Added my site to google webmaster tools. I think I did everything I need, but I only get very low organic exposure even though there are quite a lot of backlinks to my site, and the quality of content is really decent as I'm not taking any black hat shortcuts here.

Today, over 6 months passed and google still thinks my domain is a pointer to a different site.

By the way, I did audited my site and my hosting account, there is no chance that it actually points to that domain somehow.

Try create the page which NOT exists on the second domain.
Get the strong links to this page.
Wait for result.

Cheers, Greg.