well your DM and you were kind of off on this one, your right your looking for foot prints to locate him, so that would be a search check to locate where he could be at not really spot. Search is an active function spot is more " oh whats that" out of the corner of your eye. That said here is the problem with your idea.
You look for foot prints and you see several dozen foot prints, yours, your partys and his(gonna assume fight was going on since you didnt really say) and possibly others have been here. So now you have half a dozen foot prints in the room so which one was it? only some one with tracking could probably discern for sure.
Essentially speaking he was kind of right in why you couldn't just shoot him, but partially wrong as to the reason why. Its not about rules but common sense here, you knew what he was doing and you know what he did so your trying to " locate " the enemy but using foot prints? not best tactic since are probably dozens of foot prints in the area. Now if you have tracking and time to use it yes i think you could locate him.
just my opinion at least thats how i'd handle it as a DM.