It may be unnecessary to vectorize your raster at all. Access to raster data can be very fast and it may be worth having a try by selecting random points and checking if they hit the data in your raster. If point finds a hit, accept it, if not, discard. Continue until you have enough points to fill your sample size. If each query to raster data is fast enough it can be good strategy to sort the results afterwards instead of using time for preprocessing.
There must be effective scripting methods in ArcGIS for checking the pixel value at a certain location. It is also for sure possible to make the script to discard tha nodata hits immediately because nodata value is known. This gis.stackexchange question deals with it. I demonstrate the workflow with gdallocationinfo tool http://www.gdal.org/gdallocationinfo.html.
Lets find some sample image from the web. This site seems to have some images http://www.mapmart.com/Samples.aspx and we will have a try with the CONUS 10m m sample http://mapmart.com/DownloadArea/Mapmart_Samples/CONUS_10M_Sample.zip. It is a zip file which contains tiff file "CONUS_10M_Sample.tif". We do not need to download and unzip it because GDAL can access images directly from the web, even if they are zipped. We can demonstrate that at the same.
Acquire a fresh GDAL version and open a command shell where you can run gdallocationinfo. Here is a command to test with:
gdallocationinfo /vsizip/vsicurl/http://mapmart.com/DownloadArea/Mapmart_Samples/CONUS_10M_Sample.zip/CONUS_10M_Sample.tif 100 100
It will take a while but you should get a report:
If this was your image you would accept the random sample point (100 100) because obviously it is not nodata.
The gdallocationinfo query is slow but don't get frightened. Now it is decompressing some part of the zip file and reading some part of the geotiff and all this over the internet. With local image it would be must faster. Making an arcpy script could make it faster again. But if you deside to try this method make sure that your raster is tiled for making random access to some random pixel fast.
It may be good to know also for other geospatial needs that GDAL can read data from the web and from zipped files with /vsicurl/ and /vsizip/. They can be used with gdalinfo, gdal_translate, ogrinfo, ogr2ogr etc.
If you find that process would be faster if nodata-areas are known beforehand I would first separate nodata pixels for example by creating an alpha channel and vectorize the alpha channel into nodata-polygons.