1. Try to reuse
Reuse is always better than recycling or disposal because 1) it saves energy that is used in the recycling process and 2) it saves energy and materials for manufacturing and transporting new or recycled envelopes.
The most simply way of reuse would be to relabel and resend, but you can also reuse the envelopes for other purposes, for example as knee pads for gardening work. If you have lots of envelopes you can give them away to friends and family or on websites like freecycle.org.
2. Check with your local recycling facility
I heard that there are a few recycling companies that accept paper/plastic-composite materials. Although they seem to be rare, it doesn't hurt to check this first. While you are at it also check which types of plastic your local recycling facility accepts (for the next step).
3. Try to separate the paper and plastic
You mentioned that in your case it's impossible to separate the paper and plastic and for some types of envelopes this is very true, but sometimes cutting the envelope open first with a scissor gives you better access to the bubble wrap allowing you to separate it after all. However separating only makes sense if you can recycle the paper and/or plastic.
If you can separate but the plastic isn't of a type that is recycled by your local recycling company, you can try upcycling plastics by melting them into something else (see also Fusing plastic bags). Be careful when you do this, because melting plastics may release toxic fumes!
4. Check with the envelope manufacturer/sender
If you can't separate the paper and plastic or if you can't find out what kind of plastic was used (most likely it's LDPE), you could try to contact the envelope manufacturer. They should be able to tell you what kind of plastic it is and perhaps provide alternative recycling options. If the manufacturer has no good recycling options urge them to become more environmentally aware. You can also contact the envelope sender and ask them to start using recyclable bubble mailers.