Fullscreen slower than windowed? What did I do wrong?

So, I was messing around with my scene engine last night and on a whim, I
wanted to see what the performance would be like if I switched to
fullscreen. Now, since (at the time) I was using nothing but software
surfaces, I expected basically no change in performance. Imagine my
surprise when my application slowed to about 1/3 the speed in windowed
mode.

I tried playing with all the flags I could SDL_ANYFORMAT, SDL_ASYNCBLIT,
SDL_HWSURFACE, etc, etc, with minor changes in speed, but the same overall
unbelievable drop in performance.

This is on WindowsXP with SDL 1.2.8, btw.

Does anyone have any suggestions as to what I might be doing wrong that
would cause this?

I thought maybe it was because I was using a lot of alpha-blitting, so I
changed my surfaces to use colour-keyed transparency instead. Yes, it
went a bit faster, but not tremendously. I tried changing the display
colour depth, asking for the “best mode”, etc, but it was dismal under all
conditions.

Just soliciting any suggestions for what I could look in to that would
cause fullscreen to be so much slower than windowed.