I managed to get MySQL running with php and Apache on windows. I can't remember much, but I'm sure I just downlaoded the windoze version from mysql.com (it was quite hefty if I remember right!), and installed it. IT asked for some things during installation, and then I installed a windoze tool (WinMyAdmin? something like that), and when I run it from a shortcut on the desktop, it automatically boots up th MySQL server (I have to start Apache first of course!).
Are you sure you got the Windoze version? Did you put your path to MySQL in your PATH line (I think you had to anyway, in the autoexec?). What happens when you go to the command line and type mysql ? (or was it mysqld? :-\ )
Try downloading that windoze tool, it's quite helpful. I think there's also detailed docs for installing in windoze at the mysql site.
Sorry I couldn't be of more help
Danny