以下に簡略化された再帰的な方法があります。
private List<string> data;
public string Method1()
{
    data = new List<string>();
    //When Method 1 gets called first time there is a problem
    //When Method 1 gets called from Method2 problem is fixed
    if (problem)
    {
        data.Add("prob");
    }
    if(data.Count > 0)
    {
        return Method2()
    }
    else
    {
        return string.Empty();
    }
}
private string Method2()
{
    return Method1();
}
Method1がMethod2から呼び出されたとき、data変数が再初期化されて、以前そこにあったものが消去されると思いますか?