Personally I do not like the random point algorithm in ArcGIS. Alternatively, use Geospatial Modelling Environment's (GME) genrandompnts function. You will be able to identify specific polygons where random points will be excluded (see highlighted area in attached .jpg). Best of all this software is free.
GME provides you with a suite of analysis and modelling tools, ranging
from small 'building blocks' that you can use to construct a
sophisticated work-flow, to completely self-contained analysis
programs. It also uses the extraordinarily powerful open source
software R as the statistical engine to drive some of the analysis
tools. One of the many strengths of R is that it is open source,
completely transparent and well documented: important characteristics
for any scientific analytical software.
In ArcGIS, this can be done with Create random point if you have spatial analyst or 3D analyst or Advanced(ArcInfo) licence
select each shapefile as "constraining_feature_class" and set the "minimum_allowed_distance"to 250 m.
In QGIS, from what I know, you can use "Vector ‣ Research Tools ‣ Random points" with a constraining feature class, but not for distance. Again, you can use this tool in a loop to add points one by one until you reach the required number.
On the other hand, a solution for simple random sampling with distance contraint is to recursively add your random point and erase the buffer around your random point from the feature class until all your features are completely erased. As mentioned by @Whuber, this will not optimize the number of sample points, but you can control the number of points per strata.
Finally, the optimal number of points with a distance constraint can be achieved by systematic sampling : create a grid (with fishnet) with evenly spaced points (in your case 250 m) and randomly select a rotation angle and shift value betwen 0 and 250 in X and Y direction. This will optimize the number of point samples (and you could randomly subselect some points to reach a given number inside each startum). However, note that systematic sample could be biased because of the spatial autocorrelation.
Best Answer
You probably need to do a bit of modeling, first. How much area do you want each point to represent? You could jam an infinite number of geometric points inside a polygon. They have no area. The object you are trying to model probably does have an area. When you know that value, get the total area of the polygon, and calculate the number of objects it would take to cover 20% of that. Then, space that many points randomly inside the polygon.