I know that $500 and larger bills have been removed from circulation (and presumedly destroyed), making it hard for criminals to enact large cash transactions.
IIRC, use of such bills is also illegal.
But: what if I found a large stash of them that my eccentric uncle stuffed in his mattress. How could I go about getting credit for them without the authorities suspecting me in some illegal business?
What ever you do, don’t spend it in the store. Here is one for sale on eBay. The bidding is at $1136.00 and there are still nine days left for the auction.
Haj
According to The Memory Hole, possessing bills up through $10,000 is NOT illegal, and the treasury will still honor their face value. The $100,000 gold note is the illegal one, not intended for public use at all.
According to the US treasury:
So you can just take them to a bank and change them for a big wad of real money.
The one on ebay is a choice UNCIRCULATED example of a MULE bill.
The average $500 that a person uncovers in a relative’s bank box is in used, average condition. We buy about 50-75 of these every year from the public. We pay between $550 and $750 for each one. Depends on the exact condition. You could still take it to the bank and get $500 worth of twenty dollar bills if you prefer. Take such a bill to a coin dealer. You get a premium. We’ve paid a premium since 1968, when they started withdrawing them from circulation.
Same goes for $1000 notes.
If you have a $5000 or $10000 note, I’ll actually FLY to your house at my expense to pay you a slight premium to save you the embarassment of having the clerk at the 7-11 tell you they can’t take a bill of that size. 
Wow, just looking at the Ebay currency collector offerings is a trip. It almost makes up for the fact that Dr. Dawn Banks took down her website, which included an extensive online U.S. currency collection. It had more specimens for online viewing than just about all other online currency museum sites put together.
Nuts on you, wherever you are, Dr. Banks!