would shoeboxes be suitable as a game box?

I don't see why not. You could even market your games based upon that very fact. Call the company 'Shoebox Games' or something. Sure it's probably not the best most prestigious way to hold a game, but I do think it is novel concept.

If you use a shoebox with a separate lid, I suggest trying to find those with the "deepest" lids possible. The advantage of regular game boxes is that if they fall over, the lid won't just pop off and pour the pieces out (usually, unless you're on a city bus or standing over a storm drain). Shoeboxes, though, usually do just pop open, which usually isn't a big deal, as worst case 2 shoes fall out.

A deeper lid will make it less likely that the top will fall off. I usually find the deeper lids on more expensive pairs of shoes, though, so that might mean that the blanks are costly.

OTOH, one-piece boxes with a deep tongue like most modern athletic shoes have might work great, as they don't tend to come open easily at all (though they tend to have holes punched in them to be able to see the color/model). See the "Tuck Top" boxes at http://www.papermart.com for what I mean.

(Papermart has telescoping boxes and tuck top boxes with deep tongues, the latter of which are what I mean by the one-piece shoe boxes.)

-- Matthew