I don’t see any problem with passing post__not_in to the query.
Yeh, it might not look like a clever code, but sometimes the only way to implement some functionality is with ugly code.
Regarding the VIP page… its a meh, a specific edge case which might not fit your situation (are you doing a widget that apears on every page?) even if core wordpress caching will not handle this well, you can (and probably should!) implement your caching around those queries.
In any case, as you might have several queries to handle it is not clear how applicable the solution suggested in the VIP article. To implement such a solution (filter posts on PHP side) you will have to be ready to query in each query for the total of posts in all queries and this will bring a performance penalty of its own.
PS
I would ask again whether posts need to actually be unique and what harm is caused if they are not, is the added code complexity actually serves any useful purpose.