I am also having this problem with Subdivide Polygons on some large datasets.
An alternative that worked for me was the Generate Tessellation tool in Data Management. The initial run covered my entire project area with uniform polygons. I then used Pairwise Clip to extract the tessellation within my original polygons.
The clipping process resulted in some fragmented polygons, so I also ran the Multipart to SinglePart tool in Data Management to clean these up.