Well, at the library, I was taught to search by first name only in any state. List all found. Then search by the surname you know, in any state and list that. Next, if there are any siblings, do the same and chart them. I used Heritagequest to do this. As a library card member, I have free access to it on my own computer.
Then there is Familysearch.org. FREE. Do the same with it in charting names. Sometimes you have to look at the entire census page, top to bottom to find even a hint of the name(s) you are looking for.
I have a ggrandma that I have been searching for her past. Can't find anything for her before she married my ggrandma. Her name on the marriage bond is totally different from what her true name is. Years after I posted her surname here on Afrigeneas, and told the story just as you did, a relative of her family found it in a google search on the world web. If you aren't aware of it, a lot of these postings make it there. The cousin contacted me by internet, but to this day we have never met. The cousin lives in a totally different state. She gave me a lot of new info about my grgrandma's maiden name, but she did not have any knowledge of her. Still a little crack in the wall. Collect every deceased member in your family, death certificate. Do a search on every name and the Informants name. There are little hints on these forms. Read everything and analyze everything.
So sometimes the Brick Wall will crumble just enough to see a crack. When you get frustrated, put it down and let the ancestors come to you, when it is time. They do whisper to us griots.