My $0.02...
If you're looking for complete OO then your choice between the two stated has to be C++. That's that out of the way.
There may be other considerations to bear in mind. What's your definition of, say, "Fast"? Speed of execution or speed of development. VB wins on development time unless you need to get deep into the operating system, in which case there may be a need to drop into C++. Unless you're looking at something unusual in requirements, like a mathematical simulation, execution speed is not likely to be an issue - any PC that can run a current operating system can run VB apps fast enough.
It's incorrect to describe VB6 as "interpreted". It's fully compiled these days but it's still slower than C++. Or Delphi, which is rather more VB-friendly (i.e. VB programmers can adapt). But that's not a Microsoft product.
It's also incorrect to restrict VB to front ends and GUIs: we have a substantial portfolio of VB DLLs running in MTS as the back end to a major system hooked up to Sybase. They all work just fine (more than I can say for Sybase!).
If your target OS environment is Win2K or greater, I'd go for .Net. Then your C++ guys can use a decent C-based OO language (C#) and the VB guys can move up to VB.Net. Neither of which can be acquired instantly but at least you're starting out with today's technology, not yesterday's.
As I said, my $0.02...
Mike