St. Maarten diving isn't the greatest, but if you're there it's still worth doing. I'd actually recommend Ocean Explorers on the Dutch side. Haven't dove with them personally, but I understand it's now run by a guy named Jefferson who was a spectacularly skilled, passionate, and friendly divemaster at Dive Safaris when my wife and I were in St. Maarten in 2005, and from what I hear they've kept it small (6-8 people on the boat type of deal).
We've also dove with Pro Divers out of St. Kitts, although in that case it was because they were the op that came out and met the Windjammer (Polynesia) cruise. Austin was the main guy's name, and I think Margot was his wife? Anyway, that was much earlier in our diving life, so we were renting everything, but we sincerely enjoyed the dives.
I don't have advice on the other islands in the OP's list, but am watching this thread closely - starting to collect ideas for a spring 2008 trip and right now Dominica is high on my interest list along with Belize or one of the ABCs...