Why all Indian rupee notes are accepted in Nepal and Bhutan, except 500 Rs and 1000 Rs? Why spare those two notes?
India had tried to curb unauthorized trading between these countries by requesting they ban them.
However, as of 2013, Nepal and India have agreed to allow 500, 1000 notes again.
The Bhutan Monetary Authority also banned it for similar reasons.
However, as of January 2015, the RBI has also allowed travelers to take these notes to Bhutan.
So yes, that used to be the law, and it was to curb unauthorised trading, but that ban has now been lifted officially.
As Mark Mayo's answer states, these two denominations were "banned" (either officially or unofficially) in the two countries due to issues with counterfeit notes. Other denominations were not banned since most fraud on high value items / purchases would involve these two denominations.
While a lot of travel websites and guides state these are still banned, this is old advice. In practice, trading in these two denominations never really stopped. As of 2015, even government shops and agencies in Bhutan accept Rs 500 and 1000, for instance.
Having said that, there are very strict controls on export and import of Indian currency by non-Indian nationals (excluding those of a neighbouring SAARC countries). So you may find, depending on your nationality, that the point on whether those denominations are accepted is moot because you're not allowed to take Indian rupees anyway.
Both the governments(Nepal and India) have agreed to permit the use of INR500 and INR1000 notes. So it is totally legal to carry INR500, INR1000 notes to Nepal if you are going to Nepal.