We are trying to come up with a Package structure that will work for our company.

If anyone has a Package structure that has worked well for your company or any structures that we should stay away from, would you share it with me?

Generally, I try to separate public (outward-facing) and private (inward-facing) services into separate packages.

And for public services, I generally categorize them into services that are common across trading partners, and services that are specific to a particular.

For private serivces, I generally categorize services by function and/or backend system.

Finally, if there is are services that can be shared between your trading partners and your organization (e.g. generic utility services), I move these into a separate package.

Here is an example package structure using these guidelines:
MyCo_Pub_OrderEntry_Common
MyCo_Pub_OrderEntry_Partner1
MyCo_Pub_OrderEntry_Partner2
MyCo_Pub_InvMgt_Common
MyCo_Priv_OrderEntry_SAP
MyCo_Priv_OrderEntry_Common
MyCo_Utilities
SharedUtilities

This is a very general guideline…every integration will have different requirements though…

The package is generally the unit of migration/code promotion (and might also be the entity that you check into a version control software), so you will want to make your package structure reflects this. In other words, the package structure should be granular enough so that you can migrate and what you want without affecting other development/testing efforts, and also so you meet your version control reqts.