Maybe regions is my only option, although, some said to me that if my form used the opacity property (which it does, depending on the user setting for the application), the black flicker would still be a problem. My problem with regions is that I want to turn my code into a library and it will be harder to make it like this instead of simply providing a background image.
Layered Windows is not an option since it doesn't fully support lots of Windows Forms controls to be added to the form itself and this is very important for my application. The last example on this page shows exactly what I wanted to achieve if I were to use Layered Windows but it has some compatibility problems.
WPF is also not an option for now... That was my first choice long a time ago, but since the ClearType rendering in WPF is much worse (ugly) than the Windows Forms one I don't want to use. I hate text rendered by WPF, that's what's holding me back from WPF applications.
My current painting is done on OnBackgroundPaint(), it's basically the same as OnPaint (sort of).