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. :-(