Are the plastic bags inside the LEGO box recyclable?
According to this bricksetforum thread (and also true of the LEGO sets we have around right now) the LEGO bags are #5 plastic which is accepted by Whole Foods and some municipal recycling services.
This thread
has interesting commentary on bag packing considerations.  Not surprisingly LEGO Group is optimizing for efficiency and dependability.  The bags and their weight also affect the QA process which includes weighing the bags.
2021 update - the future is getting here
LEGO is reportedly moving to paper bags.  This is a double win of going with a renewable resource and wider recycling availability.  LEGO themselves have a page on their sustainable packaging that says:

We will begin to test paper bags in our boxes which means goodbye single use plastic and hello recycling bin! First, we will trial recyclable paper bags that are made from Forest Stewardship Council certified paper. They will be designed to help children understand the importance of recycling and ensure they have the best possible play experience. Our new bags will be phased in over a four-year period from 2021.