I know you'd prefer a non-folding board, but since you say that's not a deal-breaker, I'll point you to the ChessMate TravelMate Deluxe set. It has nice wooden pieces and quite strong magnets. If you watch the video available at that link, at about 40 seconds in the board is turned upside down and shaken pretty vigorously, and the pieces all stay in place; it's no trick. The downside for the set is that it's pretty pricey, but I do own this one (like in Wes' comment, I received this set as a nice gift) and I can say first-hand that it's a pleasure to use. They also have some other more and less expensive travel sets that I'd guess are of similar quality.
In fact, I see that they have a non-folding set as well: TravelMate Box. It's just as pricey as the one I mentioned, and I can't vouch for this one myself, but from their description at least it seems that it's pieces have the same material and magnets as the one above.
