I got it working after lots of time reading manuals, guides and forum posts. So it will be able to get it to work, the questions are when and why it doesn't work now.
Since you are using MySQL 5.x and PHP 5.x you should use mysqli instead of mysql. It have prepared queries and other stuff to let you write queries safer and easier. But it should work with both, that is not the problem.
Now to the actual problem. How does your extension_dir look like in PHP? In phpinfo it should look something like this:
extension_dir C:\Program\PHP5\ext\
And of course the actual extension should be in that folder. Another thing to look for in phpinfo is path (one below Apache Environment and another below Environment). The path to mysql should be in there.
PATH //Other paths//C:\Program\MySQL\MySQL Server 5.0\bin
PHP Variables also contains a path to MySQL:
_SERVER["PATH"] //Other paths//C:\Program\MySQL\MySQL Server 5.0\bin
And last there should be a whole section with information on MySQL
Sorry for this post giving pretty much information but not many answers. To be honest I don't know for sure what to do next, just thought that it might give some clue if one or more of the paths are missing.