Personally, I'm down with
Sectorlink. I don't have any affiliation with them either; just a dedicated box, and I've been a customer for over 2 years (the fact that they've even been around that long should tell you something right there, based on the way hosting companies tend to fly by night these days).
Anyway, they support ASP and MySQL. They only offer 1 database by default, but you can always ask for another one; they're usually accommodating to requests, no matter how strange. I'm not sure if they charge for the second though, since we use either Access or MS-SQL, other than for the odd vBulletin forum.
The support is absolutely amazing; if it's something relatively easy to fix, like updating an FTP login/password, it's usually done in less than an hour. They've never taken longer than 24, and the support request I made was a rather odd one, so I was expecting it.
They're a great company to deal with and they're not going anywhere anytime soon.