First, make sure none of the software you plan to use has any special requirements for specific package versions.
If you're using Linux and you're using a distribution that has proper package support (e.g. Debian with apt or CentOS and yum etc. etc.) then use the distributions supported package.
This will allow you to easily update your machine.
Personally I would go with the latest and greatest versions available to you of MySQL version 4.0.x, Apache 1.3.x and PHP 4.x.x
MySQL 4.1.x and PHP 5.x.x are recently released. Apache 1.3.x is standard and very well supported.
Apache2 is stable, works well and has some nice features and the documentation is nicer Beware of Apache2 with some of the in-built modules, e.g. mod_perl2 still has some issues. Apache2 is great, but if you're not completely confident in running a separate version, I'd hold off until your distribution ships it by default (I don't think too many are currently, although correct me if I'm wrong)
If you're using Windows, what you've suggested sounds completely sane to me.
Value for money dedicated servers
at Rack365 - http://rack365.ie/