Randomly generate the rectangle. For each existing rectangle, create a Windows region and see if the new rectangle overlaps it. If so, start over with another random rectangle.

This is a common strategy for picking constrained random items.

    Do
        Pick item randomly ignoring the constraint
        If the item satisfies the constraint, Exit Do
    Loop

The catch is you need to be certain that you will eventually find an item that satisfies the constraint. For example, suppose you use this method to select N items from an array.

    For i = 1 To N
        Do
            Pick random item in the array
            If the item has not yet been picked, Exit Do
        Loop
    Next i

This works well if N is much smaller than the number of items. E.g. pick 10 items out of 100.

It is slower when N is close to the number of items in the list. E.g. pick 90 items out of 100.

It is a disaster if N is greater than the number of items in the list. E.g. pick 101 items out of 100.