I can't speak to why the data is not included on data.gov, but CMS.gov (the site for the "Centers for Medicare and Medicaid Services") has long been a source for Medicare/Medicaid data. Unfortunately, it is sometimes not in the most machine-readable format.
CMS.gov - Research, Statistics, Data & Systems is probably a good place to start.
The Medicare program has a spiffy new data site although it seems to be limited to service provider comparison data, which is not what you asked for (in addition to not being Medicaid)
I see that data.medicaid.gov exists, and is powered by Socrata, but it is not open to the public. :-( Also healthdata.gov which may have hidden gems? I found it pretty clumsy to search, and unfortunately, don't have your motivation to root down to the actual dataset...
Note: in a private conversation with a friend who works for 18F, I was told that data.gov is specifically meant to be a catalog of existing data, even if it isn't available for download. The fact that it's labeled "public" may mean that there would be little friction if you made a FOIA request, or it may just be an error in handling the metadata, or a lack of nuance in the available values for the "access level" field. He recommends contacting [email protected] to get more information.