Here is a paper that may help in beginning to drive your selection of distance measures. Take note of table 1 (pg. 4), copied below.
On geodesic distance modeling and spatial analysis (2004) - S. Banerjee
I would suggest that if you intend to use inter-UTM zone distance computations you should be using a geographic measure. Likewise, the spatial distribution of the points to roads within the UTM may be sufficient in the N/S extent to warrant the use of geographic distance measures.
The real question needs to start as: How accurate do my measures need to be? How many measures will I be making and is the added computational cost of a geographic measure inline with the required solution speed?
Edit for the comment:
The answer goes back to your accuracy tolerance. If I needed to compute in planar space over a large distance (3 UTM zones at mid latitudes is sufficiently large) with a high level of accuracy I would likely use a sinusoidal projection. The distances computed using a gnomonic projection are only completely accurate 'from a single reference point' (ref. as above). Are you only measuring from a single point in each UTM zone? If so, use the gnomonic projection. Otherwise, think about computing chordal distance, using a sinusoidal projection, or accepting the accuracy issues.
Edit for the additional comments above:
Given the accuracy requirement without any constraint on potential distance measures you really should be using geodesic measurements. Additionally, the gnomonic projection is not azimuthal equidistant, it just happens to draw the great circle curves as straight lines. As an alternative to geodesic computation you could reproject your data centered on the origin point of your measurement into an azimuthal equidistant projection*.
Having done this for a project involving 20,000+ points and some buffering, it is not efficient to perform for extremely fast lookup. It is a one time, let it run for a minute or so operation.
If the extent of your map falls within 2 UTM zones, and you are required to use a UTM projection, you could either:
1) Choose the defined UTM zone that more of your map extent falls within. For example, if you are between zones 34N and 35N and more of your map coverage is on the 34N side, create your map in the standard EPSG 32634 and specify that this was used.
2) Locate the center of your map coverage extent, and set this longitude value as the central meridian for a transverse mercator (UTM) projection. Provide the projection parameters to your publication (as long as nonstandard projection would be acceptable).
Best Answer
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.