I would guess that something with that is fishy -- as I said, its not super fast, but I know for certain that it can keep up with 800x600x32bit color at more than 60fps, because I've done it before, circa 2004 on one core with about half the speed of any single core we have today. Unless they've routed GDI et al through DriectX under the hood these days and that's made some use-cases slower (and it may well be), I can't imagine why StretchDIBits would have trouble keeping up. That's my experience at least, you probably know better than I what to expect given the source/destination formats you're dealing with; I just think its suspect that StretchDIBits is the bottleneck from what I know.
_All_ rendering on Windows is routed through DirectX, period, without exception. They don't even make non-DirectX graphics drivers anymore.
The GDI functions used to have special drivers that would hand-optimize various calls, possibly using the dedicated 2D render unit on the graphics hardware (which don't exist on most modern hardware anymore).
Since those drivers don't exist for new hardware and aren't supported at all anyway by Windows Vista and up, most of the GDI routines are now just basic no-brain software implementations that only route through DirectX at the lowest levels (e.g. blit to a texture, render quad). The actual scaling and format manipulation is mostly all in software and the actual texture blitting is likely not even close to as fast as a naive hand-written version would be. GDI is dead (and unlike many other such claims that are a bit premature... no, GDI really is completely dead). Don't use it. If you need plain 2D rendering use Direct2D, otherwise use Direct3D. There are a bunch of libraries that provide simple 2D rendering and compositing and use the most appropriate hardware backend for a multiple platforms, like SDL2, SFML, Allegro, etc.
More information on GDI and its dead-ness since VistaBenchmarks of GDI on Vista and up showing it's far slower nowThere's plenty of other easily searchable articles online about this all too, should you care.