coordinate system - How to compute the bounding box of multiple layers in lat/long?

I am writing an application to performance test all kinds of map services, primarily AGS 9.x, AGS 10, and WMS 1.x.

Part of the application involves generating random bounding boxes for individual requests, within the service's full extent. This part is working fine for geographic and projected coordinate systems when the service's full extent is known (e.g. through an AGS service's fullExtent property).

My problem is with WMS: each layer in a GetCapabilities response can define its bounding area in >= 1 CRSs. Some parts of the application need to know if a service's CRS is geographic or projected, so in order to remove ambiguity in WMS I am always using the layer's LatLonBoundingBox which is always defined and in EPSG:4326. I then have to calculate a full service bounding box based on all layers that go into an individual request (which are randomised). This is where it gets tricky.

I am getting lost because for each lat / lon bounding box the LLx (lower left longitude) could be a larger or smaller number than the URx (upper right longitude), depending on which meridians it spans. Every time I start drawing square or circular diagrams I think I have an approach figured out, and then find a case that ruins it and my brain turns to mush.

I am going to keep thrashing at it until it works, and if I get a solution post it here, but I'm sure there has to be an accepted and fully tested approach which would make my life easier. I just can't find it right now.