You should be able to install MySQL on just about any machine and use it as a database.

Definitly - MySQL installs and works beautifully on lots of platforms - the problem I have is working out how to licence it for deployment with proprietary software that runs on a standalone PC (not on a server). The cost of licencing the usual server version of MySQL for each installation is too high so I'm trying to find out if I can licence a cheaper version for single-user, single-PC use only and deploy this with my software. (This would replace the existing Jet (MS Access) database engine.)

Well, sounds like there might be a fairly simple answer... though I'm no lawyer, nor am I an expert on MySQLs choice of licensing, so that being said, here's my opinion:
Separate your product from the database. Offer MySQL as an option... fully opensource and free, but DO charge for the installation of MySQL (this is your service).
Also, while you do this, please plug the concept of open source software (GNU license, etc) for the benefit of the movement. Remember "free as in thought, not as in beer" --- we can all collaborate on programming and tools without losing $ on our services. Just because MySQL is free to get, how many folks actually know how to install & use it?
-jc

I completely agree with this. Whenever you can build an app that isn't backend specific, you'll win points with integraters. If you can build an app that works with the big four, (Oracle, MS SQL Server, PostgreSQL, and MySQL), you'll have a lot more flexibility. Plus, you might find that a client already has one of these servers installed and you can add your app to their installation.

As far as a standalone desktop engine... The only three that I am aware of are Jet, MSDE, and Oracle Personal Edition. I believe that you can get licensing rights for any of these, but I don't know at what cost.

Andy