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][1] is probably a good place to start. 

The Medicare program has [a spiffy new data site](https://data.medicare.gov/) 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][2] exists, and is powered by Socrata, but it is not open to the public. :-(

**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.

  [1]: https://www.cms.gov/research-statistics-data-and-systems/research-statistics-data-and-systems.html
  [2]: http://data.medicaid.gov