I think you answered your own question. Copy your graph into $G'$ and for every triple of nodes $(u,v,w)$, if NotBetween$(u,v,w)$ then add the edges $u\rightarrow v$ and $v\rightarrow w$ to $G'$ (if they don't exist already). If the graph has a cycle the problem is infeasible. Otherwise the topological sort on this new graph $G'$ is a valid topo sort for $G$ respecting NotBetween.

This is clearly $O(V^3)$ because you can implement this with 3 nested loops, then resulting graph has at most $O(V^2)$ edges, and the topological sort of $G'$ will take time $O(V^2)$.

If your relation NotBetween is not a black box and actually has some "known shape" you might be able to skip some triples and do better.

EDIT: As pointed out in the comments this doesn't work!

Copy your graph into $G'$ and for every triple of nodes $(u,v,w)$, if NotBetween$(u,v,w)$ then add the edges $v\rightarrow u$ and $w\rightarrow v$ to $G'$ (if they don't exist already). If the graph has a cycle the problem is infeasible. Otherwise the topological sort on this new graph $G'$ is a valid topo sort for $G$ respecting NotBetween.

This is clearly $O(V^3)$ because you can implement this with 3 nested loops, then resulting graph has at most $O(V^2)$ edges, and the topological sort of $G'$ will take time $O(V^2)$.

If your relation NotBetween is not a black box and actually has some "known shape" you might be able to skip some triples and do better.