I've done some tests with StretchBlt and can't understand why you're having problems.

I can stretch a 1920x1280 bitmap down to 800x450 in about 4 milliseconds using StretchBlt.

I've rewritten the algorithm in ML using Bresenhem's algorithm and I can't do any better than this in software.

I think you might be using one of the slower stretching modes. Try

Code:
CClientDC dc(NULL);
::SetStretchBltMode(dc.m_hDC, COLORONCOLOR);
dc.StretchBlt(.....
Of course this isn't as high quality as the stretching using Direct3D surfaces (and these have the added advantage of applying a gamma setting to your bitmaps) but it does work with all graphics cards.

Direct3D in DirectX9 requires that stretching be a feature of the graphics card : it's no longer available in software. So you may find older machines don't support it.

For this very reason I'm keeping my stretching in software for the time being.

If you're using a 32-bit DIB section and stretching it onto a 16-bit display this can cause a performance hit though... bear that in mind.

Darwen.