@Paul - a lot of the certificate errors we see (at least from a support perspective) stem from antispam gateways and the like, which typically leverage self-signed certificates when set up as an appliance because they anticipate communication being done on private channels between the gateway and server, though that isn't how most businesses end up actually using them! Does that align with the examples you've seen so far?
Kyle Kerst
IT Coordinator
SmarterTools Inc.
www.smartertools.com