As long as you don't try paths under /home, even a moderate amount of guessing seems safer than storing them in a user-writable file.
I'm not sure I agree. If the threat model is a user doing dumb things, there's no protection against that. If the threat model is a rogue Windows program installing bad CA certs, that particular attack would only work in Wine. Our install base is too small to consider that likely. If the threat model is a winelib program or an external process installing bad CA certs, ditto.
How many different paths are there really?
I don't know. On my current machine, there are two equally probable locations, depending on whether I'm looking for OpenSSL's certs or Apache's. On my laptop, there was one (different) location for OpenSSL's certs for one distro version, and another (distinct yet again) for another version of that distro. So I haven't done a complete sample, but on the three distros I've used within the last year, there are at least three different locations.
I don't mean to imply that the limit of the number of locations as the number of distros goes to infinity diverges, just that I haven't found a strict upper bound yet.
--Juan