My attitude is that unit tests should know about the internals of the object they are testing, and should test all of the boundary cases of the implementation. Because if you treat it as a black box, how will you ever find the nasty little off by one errors? Therefore you provide hooks for the unit tests which allow them to mess with the internals in a controlled way.

For instance suppose that you have a caching layer implemented inside the main object. So it contains some sort of object which is responsible for accessing the cache. Then I'd have a set of unit tests for the cache object (just to be sure that it works properly). And then for the main object I'd have a way for the unit test to poke inside and replace the cache object. (Test::MockObject::Extends is useful for this.) This will let you write unit tests that test exactly how the caching works, and let you verify that the result without caching is the same as the result with caching.

Now to address the "I'm not testing the same code" complaint, the code for the main object is exactly the same in the unit test and out. The code for its cache admittedly gets tampered with, but the API of the new code should be the same as the old. (After all you're mostly just delegating from the old code with some logging added.) Plus you have some of your tests running before the cache gets replaced, and you know that those don't get affected, it is only the piece where you are testing the exact caching behavior that has been touched.