Hi smasimon
I will assume that if you get rid of the partial transparency then those images will work for you. You will need to try a sample print to verify.
Both
@JeffK and
@puraidodes had good comments which beg the question why the printers are being more cooperative with you as have these soft edges is very common and they should have been able to help/accommodate. Yet such as it is.
Note the the approach I give below will work in CS4 for every situation of which I can think for how transparency is created. What it does is eliminate any partial transparency and make solid the underlying color. This may or may not be what you want. If you have a very wide width of partial transparency, then the image will appear to grow.
There may be other ways to do this yet was going for one easy to implement for you.
1) You need to make sure you have a single pixel Layer (not text Layer) that only has pixels, pixels with partial transparency, and pixels with full transparency (no color at all). This single Layer should not have and Layer Mask or Vector masks (those can be merged into the pixels pretty easily if you need help with that). Also not, that since you want to have transparency, this cannot be a background Layer (which has no transparency).
If you don't have a single Layer, one pretty fool proof way to get down to one Layer and preserve transparency is to add one empty Layer and use the Layer > Merge Layers command (won't work with a single Layer)
2) Once you have this single pixel Layer with no masks you follow the following keyboard shortcut commands
Cmd+J followed by Cmd+E (Cntl+J followed by Cntl+E for PCs)
Repeat the above pair of commands 9 times (for 8 bit depth images) if you are using 16 bit images let me know.
Every time a pair of the above commands is done, a Layer is duplicated and merged back into the original. It appears that there is no change yet with each iteration, the transparency is reduced (opacity is increased). I won't get into the math yet the smallest amount of transparency (for 8 bit images) will yield totally by using 9 iterations. It takes more interations with 16 bit files.
When done, save as a PNG with the transparency and you are done.
Note that this could be turned into an Action and run on a batch of files in a folder for productivity yet thought this would be a good starting point for you to try.
If you find that the image enlarges to big when taking our the transparency, then its still possible to do yet maybe not quite as easily. The sample I returned to you was done with the steps I provided above so hope it works for your other designs.
Hope this helps so give it a try
John Wheeler
PS - There are several ways to remove the transparency in Photoshop yet fewer in the CS4 era so chose the one way that seemed the easiest to implement with the least confusion.