My guess is that you should have sufficient encoder resolution for much better accuracy than you are seeing. I've gotten passable results with ~100 counts/rev so you should be in the correct ballpark. The tests you are running are going in the correct direction, but you can continue more tests to try to determine the issue.
- Check for missing counts: Using the arduino with hardware interrupts you shouldn't be missing counts. But then again, if the spec says 663 counts/rev, you should probably not be seeing 650. One way to check for this is to write a quick position controller, put a mark somewhere on the wheel and have it go exactly 100 turns. The marker should be more or less exactly where it was when you started. If it doesn't, and especially if the place it lands changes every time you run the test, you are probably missing encoder counts, in which case you want to investigate what's going on with the arduino.
- Check for different wheel sizes: Most odom documentation assumes the wheels are the same size. In reality, they could be different by even a few percent, which could throw things off. Make sure you are getting your wheel diameters separately for the two wheels.
- Are you using the centre of the wheels to measure the wheel to wheel distance? You should measure centre of wheel to centre of wheel. Also keep in mind that using wide flat wheels is the worst for odometry.
- Are your wheels slipping? Make certain that you do these tests on a hard grippy surface, and go slow enough that the wheel controllers are well within their achievable range.
This isn't meant to be an exhaustive list, but hopefully you can get this working without throwing out your hardware, and yes, those encoders that come attached to the motors are usually not meant to be user-replaceable, so you may have to replace the motors too.