There are (at least) two factors at play here. GPUs can utilize a post-transform vertex cache when indexed primitives are rendered. The size of this cache varies, and it's utilized during an individual draw call (not across multiple calls, as far as I'm aware, so it doesn't matter how frequently you change the buffer data in that context).
If you organize your data to take advantage of this cache (an example algorithm is here), you can see performance improvements. However, this organization has more to do with ordering your indices so that each index triple reuses as many recently-seen vertices as possible. It probably has little bearing on your specific scenario, unless your triangles, via your index buffer, are also randomly scattered about in the buffer... in which case you're probably blowing the cache often. It wasn't clear to me in your question whether or not this was the case, so I thought it worth mentioning.
What's more likely to be a problem is that GPUs also cache memory accesses to vertex data during a draw. The size of that cache is also fairly unreliably sized and it's conceivable that you could get a high miss frequency in that cache on the individual cores processing those indices into very poorly localized vertex data.
As to wether or not that's going to cause enough of a performance issue to be a red flag in your application, and particular (it sounds like) to re-engineer your algorithm to better organize the data at the expense of the readability of the algorithm... that's not something I can answer, you'll have to profile some scenarios and see.
I would personally err on the side of readable, maintainable code, though, as I think any cache missing you are going to cause is not going to be significant enough for users to notice.