They all seem to be living in the 1950s without the software to open any vector files, and they don't want to know anything about them (or branding guidelines).
This is an ongoing concern. While gradients are an issue with embroidery software when it comes to vectors and how they look, in all honesty, it shouldn't matter what type of source file that it is as long as the resolution is good (I tend to like to work 6:1, but that isn't for everyone.
The only other concern, outside of gradients, with regard to vectors is text converted to outlines/curves.
Bare in mind too, at least with Wilcom, it's bundled with DRAW (and an older one at that, X8 is the current bundled version), so there aren't many that have Adobe (I'm one of the few that actually used Adobe), especially after paying what one pays for commercial digitizing software.
They are changing colours, fonts and even wording in taglines to suit themselves.
... telling them what they can and can't have...
This one is a tricky one. There are instances where this could be legitimate and there are instances where this isn't. Rarely it's actually a question of digitizing in of itself, it's a question of can the machine reproduce it and reproduce it well. There are limitations (size is a huge one) with what will won't translate. The same design may translate "as is" at one size, but not at another or using the exact same stitch types. Each stitch type has their own set of min/max attributes. The key thing is knowing when to use what. Sometimes the correct stitch type though is not the most aesthetically pleasing.
Sometimes that can be mitigated by using different weight of thread, different size of needle as well. Not always, but those things could help.
I do tend to notice that if you are going with the mid size shops, they don't tend to swap out needles/threads for different characteristics to suite the design at hand. It's not efficient, but it also depends on if the need of swapping out is higher then the extra cost. Smaller shops tend to for the more common situations/colors and really large shops have machines dedicated (particularly when it comes to puff and the various thicknesses of that) to common applications.
With changing of fonts, regardless if it can be reproduced or not (if that is the case), that's usually a function of them needing to use pre-digitized fonts as they don't use the manual/semi manual tools.
But not not all fonts translate at the same size, that's true of pre-digitized fonts as well.
Colors is a bit of a sticky situation. Depending on the brand used, not all colors exist or exist as pantone matching. Madeira has the biggest selection of pantone matching, but not everyone uses it for everything. I mentioned about changing different weight of threads, if one goes to say a smaller weight of thread for small detail/lettering help, that limits your color choices as well as the colors available for that are less then what's available for the normal 40 weight thread. So there is that to consider as well.
Is it worth looking into digitising the logos myself?
That's going to depend on your situation as to if it is worth it or not. The technical aspects of it (min/max values etc) just take time. Finding little ways to do something at this size or that size to get something to translate and visually look the same, that is a different animal and I would suggest having a multi-needle machine on hand so you can test your designs out.
Otherwise, there is going to be a lot of back and forth as your learning and getting someone else to do test stitches.
I would suggest as your learning, get designs (either stock designs or ones that you've had digitized from others that have looked good to you) and try to replicate those as your learning. Keep in mind the sequences that are used, stitch types and when they are used and density settings.
Bare in mind, stuff like this does fluctuate and may need to be changed if embroidering different substrates. What works on a hat, isn't always going to work on a shirt or what works on a moister wickering shirt may not work well on a denim shirt/jacket etc. A lot of people try to do one size for all substrates and depending on the design and how radically different those substrates are from one another, may not be possible.
Most common combo is shirts and hats, for me anyway. If you use the typical shirt fabric type, to get it to work with a hat as well, have to consider the sequencing and density settings for hat, but when embroidering on the shirt, may have to compensate with more stabilizer. Using a hat sequencing on a shirt is more time consuming then need be, but density settings are what may get you. A hat can handle far more dense design then a shirt (as long as the sizing fits both).
This is just barely skimming the surface, just to give an idea and why it's a good idea to have a machine that you can use and not just send the pattern off to the embroidery shop. Even if you never do embroidery in house and send that portion out.
Obviously it's a whole new skill to have to learn and software to buy, but then is there a common file type we can save/export to that any embroiderer can use? Or a lot of different file types?
There are a lot of different file formats, but most commercial shops should be able to handle DSTs. Even your mid range to high end home machines can also handle DSTs, that's pretty much the closest thing to universal file format that we have.
It does not retain color information though, so you will need to send a stitch chart along with that file.
Now, there are some limitations to that file format as well as not all functions are supported by the file format. For instance, I use slow/fast commands on my machines to also help with quality of stitch out during certain sections of a design (when needed) without having to babysit the machine. Those specific commands (to my knowledge) are only available in the Barudan U?? format, not the Tajima DST format. So things like that don't always translate.
With regard to software, bare in mind, anything sub $1k in price is going to tend to be more reliant on auto conversion and it's also considered home/hobby software. This greatly affects the quality of the output and you won't have as much ability to edit what's going on (and due to that, sometimes people don't even think it looks bad). There is one exception to this and that is an open source extension for inkscape, but it is geared to people that only exclusively want manual/semi manual digitizing, there is very much a steeper learning curve.
I can go on a rant as to how bad it is to have auto converting available on the cheaper packages and what they had done to the digitizing trade as a whole, but I'll spare you that.
Software in this industry costs, a lot. Adobe is peanuts to the cost of a fully feature commercial software. Just be aware of the sticker shock.
Given the higher cost for software, that could also be playing a part as to the issues that you are having as well (unless they are going the cracked software route) as the cheaper (and this is relative) you go, the less abilities that one has. And if they are at the price of Ps or cheaper, that does limit to what they are able to do.
I don't know if that is the case or not, just a possibility.
Lot of stuff left to go through, but this is already longer then my normal posts, so I'll leave it there.
I hope this was somewhat helpful.
If you have any other questions, don't hesitate to ask.
