Actually the word you mean is "Fearsome". 'fearful' would mean they themselves are afraid which is the opposite of what you mean.
Fearsome means you DO NOT want to run into them because they are formidable and might be known for doing horrendous things to their enemies.
You could use scary but that tends to lean more toward a movie type of scary.
edit: Balls! I type to slow.