Soft-CPU verification
The whole issue of CPU verification is super large and difficult.  There are people who make a career out of just this.  I'll just give you the overview...


Write an assembly language program that tests every instruction and every tiny detail of every instruction.  For example, when testing the ADD instruction you might test it with numbers that are both positive, both negative, and one of each (twice).  You would then test the carry flag, the zero flag, etc.  Other special features of the CPU (like branch prediction, etc) would have their own special part of this test.
Write, using C/C++ or something, a model of your CPU.  This is your virtual CPU.  This is also your "golden CPU", meaning that this is the CPU that everything else is compared to.  Ideally the person who wrote the VHDL is NOT the same person who writes the C/C++ model.
Write/Create a system where you can run the C/C++ model and the VHDL model side by side, and compare the results on a cycle-by-cycle basis.  Run your assembly program from Step 1 and make sure the two models match.
Run your two models on random "instructions".  Basically, fill "ram" with random data and execute that random data as if it is real instructions.  Run the same random data on both VHDL and C/C++ models and compare the results.  This C/C++ model would run on some workstation and/or server (not the new CPU itself).
Setup a machine, or several machines, to repeat step 4 essentially forever.  Even if your CPU is "finished" and has been in production for a year or more you will still be running this test.  
Repeat these steps whenever there is more stuff to simulate.  For example, you would run it on the post-route VHDL with timing when that's available.


There is no guarantee that comparing the VHDL and C/C++ versions will catch every single bug-- but there really isn't a better way.  And testing the CPU on random instructions takes time, but that is also very useful.  The only real alternative to this is to hire lots of people to just write code all day to test different parts of the CPU-- and the bigger companies do this, but they also do the random data stuff too.

For a single person writing VHDL code, usually it is just step #1 that is done.  But if you are going to sell the CPU then at least some of the other steps should be done (and really, you should do them all).