First off, you ARE starting from the begining of the tape by using the command mt -f /dev/rmt/0m rew. Check out the man page for mt. Since you probably use this command every day, you would not be appending to the tape at all (if the tar command had worked).
But see Error tar'ing files to tape. A tar archive, created with Sun's tar program is limited to 8,589,934,591 bytes. More tapes won't help. Try another program.