Yes, client caching in visitor group criteria is also described in the article that you referenced: https://world.episerver.com/documentation/developer-guides/profile-store/profile-store-api/segments/#caching

I agree that 5 mins can be too aggressive caching if your segment depends on visitor activity that happens right now. 
What caching time would sound reasonable from your perspective/based on your use cases?

As you know, event-based segments are calculated and cached for 1 day. We enable developers to use KQL, which allows building very complex queries. It may be tricky to figure out which query is safe to run many times, and which one creates a heavy load on the system and can affect other customers. It depends not only on the query, but also on the amount of data and the values that are stored and analyzed, and it can change over time and depend on visitor activity. 
To start simple, we limited it by caching for 1 day. Recently we discussed cutting cache time to 6 hours, which (hopefully) should solve most of the use cases, except for real-time segmenting based on current activity. As an option, it could be a self-learning system, that adapts caching based on existing statistics of previous executions. However, it is not supported at the moment.

With that said, it's hard to guarantee that querying events for each visitor click will perform well because it depends on specific queries, data amount, and values. I would still recommend caching information on the client to avoid tons of API calls.

In general, using POST api/v2.0/TrackEvents/preview can be more efficient and provides more flexibility and features by using KQL. See best KQL practices for improved queries here: https://docs.microsoft.com/en-us/azure/data-explorer/kusto/query/best-practices

The idea of POST api/v2.0/TrackEvents/preview endpoint was to enable developers to preview KQL queries for filter definitions, so it has a limit of returning up to 1K results. This is fine for preview or running aggregation queries, but may be a problem when trying to get the full list of devices in a segment.
As a workaround, consider running the query for the specific device ID of the current visitor, so the query basically could just check if the specific device matches specific rules in KQL. That would require executing queries for the current visitor and for each segment/audience that you need to match on the page, which is far from ideal. And in general, it requires custom segmenting implementation.

As an alternative for event-based segments, you can use profile attribution and create segments based on OData-like queries for profiles.
Basically, instead of querying events, you can store the required information under the profile.Payload in a simple form and verify those values in your segment OData-like query. Btw, you can create filter definitions for profile-based segments too, to reuse query templates for several specific segments.
Using standard profile-based segments is preferable, comparing to complete custom profile implementation because you can re-use these standard segments in existing VS criteria and in Marketing Automation (Campaign). 

Profile segments are NOT cached on our backend. 
The only caching is those 5 mins in the visitor group criteria, that you can avoid in your custom criteria implementation (although I still would cache when possible). To workaround 5 mins cache on the client, you can create your own VG criteria and try using MatchByProfileId and/or MatchByEmailAddress endpoints to verify if the current visitor profile is part of a specific segment. See the Swagger specs of the Profile Store API.

Another option is querying profiles directly using Profile Store API, without creating a standard segment.

Anyway, ensure that the visitor profile exists when you store any attributes in the profile payload. Keep in mind that events are put in a queue for processing and the corresponding profile may not exist yet immediately after the first events from the new visitor.

Please note that described options are workarounds and not officially supported or verified. 

I have been digging this out for a couple of weeks and came to the same conclusions as you are suggesting within the current limitation and technology stack.