Easier way
A much easier way to cut VAT fraud would just be to abolish VAT (or at least, drastically reduce its scope so it becomes the exception as opposed to the norm). Tax people at the moment they earn their money, not when they spend it. This would also have the benefit that those who earn the most money, pay the most taxes.
An across-the-board switch to a "pay first / claim back later" model (as mere mortals already have to do) also would be effective; but it probably would be overburdensome (and in any case, could still be "gamed" as long as disparate currencies exist within the EU).