There are many ways to label nucleic acids for probes (Summary of Methods).
While there are cases where Klenow fragment-mediated fill-in should sufficiently label both strands of your probe, there are many others where this would not be enough. Here are two illustrative, although somewhat contrived, examples:
Example 1: Double digest with 5' and 3' overhangs
Imagine you did a double digest with BamHI and KpnI to release your probe sequence from the plasmid in which you propagate the sequence. BamHI will give you a 5' overhang, but KpnI gives a 3' overhang.
Resulting BamHI & KpnI double digest fragment:
5'- GATCCNNNNNNNG - 3'
|||||||||
3'- GNNNNNNNCCATG - 5'
Subsequent treatment with the Klenow fragment + $\alpha$P32-dATP + cold dNTPs will both fill-in the 5'-overhang (Klenow's 5'->3' polymerase activity) and remove the 3' overhang (Klenow's 3'->5' exonuclease activity).
Post-Klenow reaction (bold = new bases, * = radio-labeled nucleotide):
5'- GATCCNNNNNNNG - 3'
|||||||||||||
3'- CTAGGNNNNNNNC - 5'
*
At this point only one strand is radio-labeled so the terminal transferase step is needed to add a label to the top strand.
When using $\alpha$P32-dNTPs, you often pick only one base to be radioactive (eg dATP as above). Sometimes you also just spike the reaction with radioactive dNTP leaving a population of cold dNTPs to be used most of the time. In either case you now have the chance of not incorporating only non-radioactive bases.
Example 2: Fill-in reaction that fails to incorporate $\alpha$P32-dATP:
Imagine a digest with PspI and want to fill-in the 5' overhangs using $\alpha$P32-dATP + cold dNTPs. PspI recognizes CCWGG sequences where W is either A or T so that some fill-ins will incorporate the $\alpha$P32-dATP, but others will not.
Possible digests and fill-in reactions:
5'- CCTGGNNNNNNNNNNCCTGG - 3'
||||||||||||||||||||
3'- GGACCNNNNNNNNNNGGACC - 5'
|
Digest with PspI
|
V
5'- CCTGGNNNNNNNNNN - 3'
||||||||||
3'- NNNNNNNNNNGGACC - 5'
|
Fill-in with Klenow + hot dATP + cold dNTPs
|
V
5'- CCTGGNNNNNNNNNNCCTGG - 3'
||||||||||||||||||||
3'- GGACCNNNNNNNNNNGGACC - 5'
*
Again you are left with only one strand being labeled (or no strand labeling if the sequence was 5'- CCAGGNNNNNCCTGG - 3') and a need for the terminal transferase step.