1) I am assuming you know and use the better papers for inkjet printing. Take some papers that this lab does not use, and would be considered the equivalent of the paper/s that you use to do digital prints, and have them use these papers to make the prints with. Or, take over what is considered to be perhaps a pricey, but also best type of paper that can be used for digital printing for the contact look and likewise, the best type of paper that can be used for analog prints. I believe AZO is still around and many felt it was up there as the distinguished "best" for contact prints. Find something like an AZO that your labl obviously would lose money on if they used it for doing the contact prints since the sheet itself is say $5-$10 for a 4X5 sheet. I have to paper research as I have no idea what these papers for digital and contact printing cost, the ones for digital that are supposed to give the look of the contact print and the best analog stuff available today.
2) Take the contact prints and try to replicate them using some sort of paper that is supposed to look like a contact print (see above) or some paper that seems to be what the machine wants to print onto to make those nice analog prints more indistinguishable to the digital prints. You have probably tried this already, but it would be an interesting thing to do IMHO, because now you are playing with different papers through the digital output and can adjust this/that/etc. as you do digitally, but can also find out what it is you need to do in order to replicate that analog print. Maybe it is possible? Maybe it is not. But if it is possible, you can indeed no longer use the printer locally and use that extra money to buy the future papers that will come out made specifically for those interested in getting the look of the contact print through a digital process.
I know it's quite a tough one to handle, but if you really want to play around and experiment with it all to see just how much you can do on your own to just how much the lab could be doing if they were using different papers than they do, and likewise, you using different papers, along with doing all you can in learning about what papers along with what photoshop and printer necessities is required to get the same analog look.
Sorry for the long one here, but I think this would be a very satisfying exercise. It would take some time, obviously, but you would be dealing with the best papers for both digital and analog paths, and have the opportunity to see not only if you can replicate and make a similarly good analog print as what you have been used to seeing from your lab, but you may actually see that the lab using such and such a paper is incredible and far superior to anything you can do digitally, while at the same time, you may find that even with these best papers for analog, you may find that the best papers for digital are able to not only replicate/look as good, but be far superior than what the analog ones look like.
Thanks and hopefully you or someone will do an experiment like this. I think it's very interesting because if you did find a paper that really did it for you (that you gave to the lab), it could open up how you look at the traditional path more. At the same time, if you do the digital path with better papers and learn that you can replicate or make better prints than those the lab did with the best papers you give to them, you can surely know the best path to go, though the blown out highlights thing, if corrected in the darkroom or simply digitally is pretty mute for having it contact printed!
Cheers and enjoy the shooting and hopefully some exercising of different papers for the lab and yourself to use!