There are actually many answers to this question – but consider the following from John Calvin:
“Our opponents ask us what faith we had for many years after our baptism, in order to show that our baptism was in vain, since baptism is not sanctified to us except by the word of promise received in faith. We answer that although we were blind and unbelieving for a long time and did not embrace the promise which had been given us in baptism, yet the promise itself, since it was from God, always remained steady, firm, and true. If all men were false and liars, still God continues to be true; if all men were lost, still Christ remains a Savior. We confess, therefore, that when we totally neglected the promise offered to us in baptism, without which baptism is nothing, we received no benefit at all from baptism… Yet we believe that the promise itself never expired…. By baptism God promises the forgiveness of sins and will certainly fulfill the promise to all believers; that promise was offered to us in baptism; let us, therefore, embrace it by faith.”
In short, Calvin reminds us, baptism is not primarily my word to God, my promise to God, but God’s promise to me. Baptism is a visible word. It invites me, summons me to believe the One who has promised to cleanse my sins through the death and resurrection of Christ. The “solution”, therefore, to someone who has not believed his baptism thus far is not to get baptized but to repent and to believe and receive the promise symbolized in that baptism.