Dealing with data that spreads across UTM Zones?

Based on the information provided I would be looking at using a different projection which is not tied to the UTM Zones, like GeoScience Australia's Lambert Conformal Conic Projection. This will have some distortion effects but they will be minimal. The distance unit is metres. It should also get through the issue of the state crossing as all agencies are meant to be able to use this projection as GA is the primary mapping body in the country. Check with your requirements as this may be an option.

The projection is available for download if not provided from this website.

Have you tried using the geography data type. That stores in long lat and returns measurements in meters. You can then use a combination of CAST to geometry and transform for display if you need to project for displaying the data.

http://www.postgis.org/documentation/manual-1.5SVN/ch04.html#PostGIS_GeographyVSGeometry http://www.postgis.org/documentation/manual-1.5SVN/ch04.html#PostGIS_Geography

Pick the UTM that most of your data falls in, and use it for all data. UTM Zones have (a half degree I believe of) overlap for just this reason. Measurements won't be too far off in this overlap zone.