"HTMLTidy executable is not available"

Assuming you've already followed the instructions at http://drupalcode.org/project/htmltidy.git/blob/refs/heads/7.x-1.x:/INST...
There are a few possibilities.

* most likely is that you are on a shared host that doesn't permit all users to run arbitrary binary executables on the commandline. This is quite normal for them to want to prevent, and you should check with your sysadmin.
However, the host may instead provide their own allowed install of tidy to be used, and you should instead enter the full path to that in the settings.
If your server is managed securely, and you don't have the authority to install executables, and the sysadmin can't provide access to it, then this is pretty much a dead end - you can't use this utility on that hosting plan at all.

* You may have the wrong binary for the OS you are on. You don't state what the server is running, or which download you used, so that needs to be checked.

* Depending on how you copied the executable up, you may need to flag it as executable. How to do that will depend on your level of access to the server, but a quick google will tell you how (probably just "chmod a+x tidy")

But, probably answer A

Yep - that's understandable.
Good job for following it up. That's exactly the sort of response that's reasonable for a shared host.
Sorry about that, but it's a dead end there.

htmltidy is a binary ... and although there have been some PHP only libraries emerge (maybe using PHP DOM XML or Querypath), that's a total rewrite and would be a different project.

The INSTALL.txt states
* This module requires the htmltidy executable for your machine to be available.

However maybe that could be made more explicit on the project page. Diagnosing whether this will work for all servers on all hosting packages is way too difficult, so requires a bit of investigation like you did here.

Eek. I spent too much of my life doing similar - which is why I built https://drupal.org/project/import_html (which followed htmltidy). It also requires htmltidy to work well, especially if confronted with Frontpa-jisms

But for thousands of pages, you really need to be developing locally then releasing, not doing everything somewhere else. Much quicker too.
Build your site on our own machine - of any description - and you can install the cleanup tool there.
Then push up the finished product. That's a totally normal process.

You should be seeing the actual message in the logs.
What do you actually see when you run that command?
"C:/Program Files/BitNami/wampstack-5.4.16-0/apps/drupal/htdocs/sites/all/modules/htmltidy/bin/tidy.exe" -v should be able to return a bit of version info.

However, if you are storing things under a floder with a space in it, there is a chance that that hasn't been properly escaped.
I'd try the old method of entering the path as

C:/Progra~1/BitNami/wampstack-5.4.16-0/apps/drupal/htdocs/sites/all/modules/htmltidy/bin/tidy.exe

*folder*

Just a quick typo.

:-)

If you are running a valid version of tidy on a valid OS, the -v flag should be printing out the version and build number.
If not, I have no idea what your copy of tidy.exe is.
It doesn't sound like the one that's normally found at http://tidy.sourceforge.net/#binaries

In the old CVS system, there used to be a /bin/ directory. In git now, empty directories are not replicated, so it seems to have gone away in the current bundles. You can make a directory called 'bin' inside the module directory ... or you can do the normal thing like can work for anyone with administrator access to the target machine : Install the executable anywhere you damn well like, or anywhere your chosen install process puts it ... then just enter the PATH to the tidy.exe wherever it is.

I can't help you choose which of the executables at http://tidy.sourceforge.net/#binaries you should use, that depends on what "operating system" you use. If you have an "Apple Macintosh", you probably want the one labelled for "Mac OS X". If you have a "Microsoft Windows PC" you need to pick one labeled "Windows" something. Based on the path you listed before, I'm guessing Windows, but you've not said what version.
If you don't know what version of Windows you have, I can't help you. If you have a version of Windows not listed there, I'd suggest you just pick one and see if it works. More documentation is available at the website page there.
As I said above, I can't understand why you'd find a version that runs without error but still doesn't return a version number from -v.
You'd have to look for support at the website.

I don't have a test machine to trace what's going wrong for you.

When it says "enable a input filter on your chosen input format". That means
* choose an input format (full HTML is fine if that suits you and it the one you use most)
* enable that filter for that input format.
You can add it to as many as you like. See the docs on https://drupal.org/node/213156