Have you already encoded the AMV? If not are they hard subbed, you can remove the sub streams from DVD or mkv and ogg files in Virtualdubmod, you can always buy it on DVD if they are hard subbed.
If you have already made the amv then cropping is the best option, do this preferably with AVIsynth. If you do choose a different program then make sure your aspect ratio is still correct. Most NLE will allow you to do this, and even some encoders do too.
If you want to paint them out then you have a few choices, the best, but longest way would be to paint each individual frame in something like photoshop, alternatively there are paint features in Aftereffects, but I would recommend that personally.