I've encountered similar situations with MODIS albedo product before, but not NDVI. Based on my experience with MODIS data (albedo and others), these datasets are not perfect, and sometimes there will be values appear which are neither within the range of valid values nor fill values indicated by the product website. My recommendation would be first to check out if the original HDF files have those weird values. Since you did conversion using HEG, it's always good to see if those values appeared during the conversion process. Then i'd recommend create a series of masks yourself, based on the QA bands and the actual values. I believe MOD13A1 product has two QA bands, you can use them to mask out pixels of lower quality according to your need. Also, since there may still be weird values even for high quality observations, you can set another mask to exclude all pixels that are not within the valid range. After applying these masks, you are difinitely going to have only high quality NDVI values left and they are within -2000 - 10000. You can then scale them down uniformly.