Path recursively

You need to specify each directory individually, the PATH mechanism doesn't walk through subdirectories.

A workaround could be a directory full of batch files (of some sort) that start the real tools with full path

Here is a workaround. Save this as "SetMyPath.bat" (or with another name):

@echo off
set dir=%*
setlocal EnableDelayedExpansion
for /f "delims=" %%i in ('dir /s /ad /o:d /b "%dir:"=%"') do set path=%%i;!path!
cmd

(Here, "%dir:"=%" is only needed to permit you to omit quotation marks around the directories with space in the names when calling this file. If you don't need this, then %1 would do instead.)

This file takes one command-line argument: the directory. It will launch a new copy of cmd.exe, where files under the given directory will be available:

C:\> mysqldump.exe
File not found.
C:\> SetMyPath.bat C:\Program Files\MySQL
Microsoft Windows [Version 6.1.7601]
Copyright (c) 2009 Microsoft Corporation. All rights reserved.
C:\> mysqldump.exe
Usage: mysqldump [OPTIONS] database [tables]
C:\> exit

In this example, the first command shows that mysqldump.exe is not on the path. After you execute the batch file, a new cmd.exe is launched, where mysqldump.exe is available. When you finish working with it, exit returns you to the original copy of cmd.exe.

If there are two copies of the .exe file under different subdirectories, the copy in the most recently updated directory will be launched (because of /o:d). In this example, assuming that the directory of the most recent version of MySQL was updated last, the most recent version of mysqldump.exe will be launched.

The batch file can be modified to guarantee that the most recent copy of the .exe be launched (ask me in a comment if you need it).