Some will say otherwise but I would suggest that you separate TDD and Unit Testing. TDD is quite a mental shift and unit testing appears initially to take time. If you consider them to be one item, there's a risk that you won't see enough benefit immediately and there will be a temptation to simply drop TDD and Unit Testing with it.
First thing is to write some Unit Tests. They don't have to be perfect at first. Just teach yourself how to test small units of code and how to use mocking to isolate components.
This is the biggest time-taker but has by far the biggest payoff. Once you notice that you no longer have to page through 14 web pages to get to the one you want to test, you'll know what I'm talking about.
For me, the big Eureka moment was a Windows app where I was trying to test a regex which required I fill in two forms before I could get to it. I installed NUnit and wrote a test around that method and saw how quickly I saved hours of testing time. Then I added more tests to deal with the edge cases. And so on.
Then learn to write unit tests well. Learn the balance between brittle tests which are quick to write and writing many many individual tests. This is fairly easy. The lesson is that ideally each test only tests one thing, but you quickly learn how long that takes, so you start bending a bit on the rule until you write a test which breaks on every code change, then you move back towards the right balance (which is closer to the former than the latter).
TDD is, as I said, a major mental shift in the way you work. However, it won't add much time to your development process once you're already writing tests anyway. And you will, I promise, see your coding style improve before your very eyes. Or rather, if you don't then drop it, it's not for you.
One last thing to bear in mind is that TDD is not limited to unit tests. Acceptance test driven design is every bit a part of TDD. Another good reason not to mix them up in your mind.
You should separate the code dealing with the web services (i.e. sending and receiving data) from the code processing the results. Move the latter code into a distinct class, making the necessary methods public. Then you can easily unit test the processing logic, in isolation from the external dependencies.
By this, you also make your code conform to the Single Responsibility Principle. As a general rule of thumb, feeling the need to test private methods is often an indication that the class has too many responsibilities, thus should be refactored into multiple classes.
Best Answer
If you want true Unit Tests, then you have to mock the cache: write a mock object that implements the same interface as the cache, but instead of being a cache, it keeps track of the calls it receives, and always returns what the real cache should be returning according to the test case.
Of course the cache itself also needs unit testing then, for which you have to mock anything it depends on, and so on.
What you describe, using the real cache object but initializing it to a known state and cleaning up after the test, is more like an integration test, because you are testing several units in concert.