MySQL is more an more a truly Uber solution to databases. The price is right (free), and the windows version (free) is totally compatible with the Unix version.
Now just in case there are any idiots out there that think MySQL can't scale, I've built MySQL databases that had more than a million records, replicated across 3 clusters of 3-5 machines (each cluster) more than 3000 miles apart. Each database (individual machine in the cluster) handled up to 70 lookups per second at peak volume. This volume of data transfer required FC storage (only 1TB per cluster, but FC was *expensive* back then) because normal RAID couldn't quite keep up with the IO.
I've had MS SQL servers that have crumbled under a quarter of that volume. For this project, the company I worked for had investment from Microsoft, so I was unfortunately required to duplicate my efforts under MS SQL as well. When we demonstrated the... errrm... failings of MS SQL to Microsoft, they didn't say another word about us using MySQL.
To save on dev time and pain, I typically design my database locally under windows, and replicate the structure to the live database (generally a linux server sitting out on the net somewhere). The application is developed using ODBC. By structuring things like this from the start I can simply flip a switch and test against either the live database, or the test (local) database.
Since just about every single programming language support ODBC these days it's a no brainer.
So, to sum it up, if you're serious about your project, take a good look at MySQL. It's a bit more work to get set up for a VB project than MS SQL or Access (hell, with .NET shit just happens if you do an install of *Everything*

) but it's *very* worth it.
On the other side of the coin, you might want to evaluate closely if you really need a database or not. Anything under around 2000 rows (depending on the data) can just as easily be dumped into a CSV file. In fact there are even some languages (Perl for example) that will allow you to bind a CSV file as if it were a database, and actually make SQL calls to it. This is another really handy way of scaling a project up to actualy using a DB before setting out and dealing with the implementation of a potentially complex schema.
Bah, orignally I was just going to point you at the windows version of MySQL and say "MySQL good! Microsoft BAD!". If you would like help working with MySQL, let me know, I've been using it for at least 8 years.