Spock's dialogue suggests that the recovery of the boots was vital, not merely to determine whether Gorkon's assassins came from the Enterprise or not, but in order to identify the guilty parties, and subsequently prove Kirk's innocence:
SPOCK: Any progress?
VALERIS: None. We have a crew of three hundred turning their own quarters inside out, but the killers may still be among them. Surely they have disposed of these boots by now. Would it not have been logical to have left them on Gorkon's ship?
SPOCK: Even logic must give way to physics. Gravity had not been restored by the time they escaped. Without the boots, they would have floated off the Klingon transporter pads.
CHEKOV: Why not simply vaporise them?
Valeris takes a phaser from a storage unit on a nearby wall.
VALERIS: Like this?
Valeris fires the phaser, vaporizing a pot. Alarms howl for a few seconds, before Valeris silences them by flipping a switch on the same wall.
VALERIS: At ease. As you know, Commander Chekov, no one can fire an unauthorised phaser aboard a starship. ...Suppose when they returned they threw the boots into the refuse?
SPOCK: I'm having the refuse searched. If my surmise is correct those boots will cling to the killers' necks like a pair of Tiberian bats. They could not make their escape without them, nor can they simply throw them out the window for all to see. Those boots are here, somewhere.
SPOCK: Ah! Mister Scott, I understand you're having difficulty with the warp drive. How much time do you require for repair?
SCOTT: There's nothing wrong with the bloody thing.
SPOCK: Mister Scott. If we return to Spacedock, the assassins would surely find a way to dispose of their incriminating footwear, and we will never see the Captain or Doctor McCoy alive again.
SCOTT: Could take weeks, sir.
SPOCK: Thank you, Mister Scott.
It's true that he couldn't be certain the boots were on the Enterprise, and that the only thing he knew for sure is that someone on the Enterprise altered the ship's data banks to indicate that two torpedoes had been fired. The notion that the assassins had beamed from Gorkon's ship to the Enterprise was therefore only a working theory at this point, as acknowledged in subsequent dialogue:
SPOCK: Klingon blood.
CHEKOV: They must have walked through it when it was floating and tracked it back here.
SPOCK: This is the first evidence that corroborates our theory.
But since the recovery of the boots was apparently the only means of proving Kirk's innocence, it made sense to search for them on the Enterprise in the hope that they could be found, rather than assuming that they were beyond effective reach on a cloaked Bird-of-Prey somewhere (where they could've been destroyed already), in which case the investigation would've been dead in the water.