Unfortunately CGAL is not suitable, and yes you do need to support it in the underlying representation and database. The litmus test for a suitable computational geometry engine is the ability to do arbitrary ellipsoid computational geometry at something like one part per trillion error, and the ability to compute intersections of very complex polygons on that surface quickly.
On that last point, you can execute an effective denial of service attack on most GIS databases with a well-crafted set of polygons and polygon intersection queries. It doesn't even require malicious intent. (Yet another thing I learned the hard way.)
Any chance you could give an example use-case or three? Sounds fascinating -- I use PostGIS and find it to be slower than I'd like day to day, but it sounds like your uses demand a lot more precision than I have call for.
For example, the intersection of n polygons could have exponentially many segments. To prevent denial of service, accuracy has to be sacrificed, but "one part per trillion error" sounds hard.
As another example, representing the intersection between two line segments without error requires a data type that has three times as many bits as the x/y components of their endpoints, so rounding has to happen here, too.
The only solution I can come up with that would not have those problems would be to subdivide a plane into grid cells of size one trillionth of whichever unit, rasterize all polygons into it do the Boolean operations at pixel-level, but that would require huge amounts of memory and processing power. And additionally it would be vulnerable to a DOS attack where the attacker sends many very large overlapping rectangles.
Lastly, huge amounts of data would require many computers to be able to work on this problem in parallel, but if an attacker sends only overlapping polygons, parallelization would be very tricky if not impossible.
