Is Graphics.CompositingMode set to CompositingMode.SourceCopy? That should cause painting the background twice to be equivalent to painting it once, since it will replace the existing alpha/color data instead of compositing over it.
I think I would call this expected behavior, actually. What I would do is render my background to an in-memory bitmap and, in the paint event, copy that to the form (basic double-buffering).
If I'm way off base, could you post a screenshot? I don't know that I'm imagining what you're describing correctly.
EDIT:
I'm wondering about your use of OnPaintBackground... pre-.NET, if you were doing double-buffering you'd catch and ignore the WM_ERASKBKGND message (to prevent flicker), render your image to an offscreen buffer, and copy from the buffer to the screen on WM_PAINT. So, try changing from the OnPaintBackground to OnPaint.
I haven't done too much of this kind of thing in .NET, but I had a pretty good handle on it before; I just don't know if it'll translate well or not!
EDIT 2:
Marc, the more I think about what you're trying to do, the more problems appear. I was going to suggest creating a background thread dedicated to capturing the screen and rendering it darkened; however, in order to remove your own form you'd have to set the visibility to false which would create other problems....
If you're unwilling to give up, I would suggest creating two windows and "binding" them together. Create a semi-opaque window (by setting opacity) for your background window, and create a second "normal" window for the foreground. Use SetWindowRgn on the foreground window to cut away the background and position them on top of each other.
Good luck!