Helmets need to be snug, and I've found that most other riders I run into are wearing helmets that are at least a size too big for them. Arai (and other manufacturers too, I'd assume) offer different sized cheekpads to customize fit. Try and find someplace that carries many different brands, and that has someone on staff who understands helmet sizing.

And forget Shoei, it sounds like your head isn't round, so they're never going to fit right.