Testing with the Leaks instrument should be part of your strategy, but not all of it. You will want to test your application from multiple angles.
My strategy towards testing tends to focus first on functional testing, followed by performance tests, and then a last round of functional tests. There's very little point in tuning performance if you have a crashing bug somewhere in your code, unless that crash is due to resource exhaustion of some kind.
Hammer on the application to try and make it break by running through every option under every condition you can think of. If that passes, I usually employ my "crazy monkey on crack" test where I hammer random buttons and areas on the screen as fast as I can to see if I expose any further crashers.
Only then do I turn to Instruments. Run the application on the device (no performance tuning should ever be done in the Simulator) using the Time Profiler and Memory Monitor instruments. Look for both performance hotspots and memory spikes, as well as memory accumulations. Repeat the same sort of testing you used for functional issues earlier while doing this.
Once you deal with the hotspots and obvious buildups, you can step down to a finer-grained examination of memory. I actually prefer using the Object Allocations instrument with its new heapshot analysis capability to the Leaks instrument for finding subtle memory buildups and leaks. The Leaks instrument tends to be conservative, and can miss some buildups. Nathaniel points out Bill Bumgarner's excellent post on the subject.
The Object Allocation instrument and its heapshots are particularly powerful when combined with the UI Automation instrument, where you can do hundreds or thousands of cycles of testing within parts of your application to make even the tiniest memory accumulation stand out. I've started to do more of this kind of testing now.
I think it works best to see this in action rather than described in text, so I'd recommend watching the video for my "Testing" and "Performance tuning" classes as part of my advanced iOS course on iTunes U. I demonstrate each of these tools and how I use them in the testing of my own applications before App Store submission. My course notes (in VoodooPad format) also describe this in detail.