What is the reason to avoid brute force method? Do you need to get hundreds of these random points in every frame?
If there is no actual performance reason to avoid the brute force overhead, I would do something like this:
loop X times:
select random point inside A
if point not inside B:
return point
# reduce area B's size and try again
make area B 30% smaller
loop Y times:
select random point inside A
if point not inside B:
return point
# quit trying and return any random point
select random point inside A
return point
The player will never notice that sometimes the NPC’s target point is closer to the previous point than it usually is.