1. Try to reuse
Reuse is always better than recycling or disposal because it 1) saves energy that is needed for the recycling process and 2) saves energy and materials for manufacturing and transporting new envelopes.
Besides relabeling and resending 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've heard that there are a few recycling companies that accept paper/plastic-composite materials. Although they seem to be very 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 it's impossible to separate the paper and plastic in your case 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 of if you can't find out what kind of plastic was used (most likely it's LDPE), contact the envelope manufacturer. They may be able to provide you with this information or with 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.