The solution was to wrap a limited set of .Net image manipulation functions into a COM enabled dll and call this dll from VBA in Excel.
By using the .Net image manipulation functions, we ended up with simple support for various image formats, BMP,GIF, JPEG etc, use of stock images as templates and a great deal of flexibility.
Excel can be "bent" to produce nice looking pictures and then the image copied to the clipboard and some VBA used to call Windows API functions to paste the clipboard into a Picture object etc.
The trouble with this approach is that is very confusing if you are not a programmer and it often doesn't yield quite the right results.
For example changing the JPEG compression level, changing this affects the "blockiness" and unwanted atrticats that occur when you compress an image with only a few colours, this is really not the sort thing that a spreadsheet cares about.
This appoach has left the client with a tool that he can use over and over again to produce completly different labels simply, and no matter how complex a new requirement it will always be able to be met by extending the dll.