For basic display items like lines, you should consider breaking them up into a few parts if you absolutely must invalidate their entire bounds per drawing cycle.
The reason for this is that GDI+ (as well as GDI itself) invalidates areas in rectangular shapes, just as you specify with your bounding box. You can verify this for yourself by testing some horizontal and vertical lines versus lines where the slope is similar to the aspect of your display area.
So, let's say your canvas is 640x480. If you draw a line from 0,0 to 639,479; Invalidate() will invalidate the entire region from 0,0 to 639,0 at the top down to 0,479 to 639,479 at the bottom. A horizontal line from, say, 0,100 to 639,100 results in a rectangle only 1 pixel high.
Regions will have the very same problem because regions are treated as sets of horizontal extents grouped together. So for a large diagonal line going from one corner to the other, in order to match the bounding box you have setup- a region would have to specify either every set of pixels on each vertical line or the entire bounding box.
So as a solution, if you have a very large line, break it into quarters or eighths and performance should increase considerably. Revisting the example above, if you just divide in half for two parts- you will reduce the total invalidated area to 0,0 x 319,239 plus 320,240 x 639,479.
Here is a visual example of a quarter splits. The pink area is what is invalidated. Unfortunately SO won't let me post images or more than 1 link, but this should be enough to explain everything.
(Line Split in Quarters, Total Invalidated Area is 1/4 of the surface)
a 640x480 extent with 4 equal sized boxes carved behind a line drawn across the diagonal
Or, instead of specifying a bounding box, you may want to consider rewriting your updates so that you only draw the portions of items that match the region that must be updated. It really depends on how many objects need to participate in a drawn update. If you have thousands of objects in a given frame, you might consider just ignoring all the invalidated areas and just redraw the entire scene.