Depends what you mean by 3D. Making a wooden jigsaw along the lines of St Pauls or London Bridge is likely to be impossible along the lines of the similar foam ones you mention. However if by 3D you mean multi-layered, either interlocking between the layers occassionally or interlocking horizontally and vertically for each piece then yes it is possible. I have made several and there are a number of them out there on the web.
The problem with them tends to be unless they are a very few pieces they are nigh on impossible to put together. They tend to be simple shapes like an apple or a maple leaf, sometimes in a shaped frame, box or container; rather than several hundred pieces over 3 layers.
Another downside to making them is that you need thick timber to start with (solid timber rather than birch ply) which therefore needs a bigger blade (#3 at least) to ensure cuts are vertical all the way through the piece. If you use a finer blade such as the more usual 0/2 for cutting puzzles the blade deflects, meaning pieces have a tendancy to go together one way only ie piece 1 must be put down onto piece 2 - putting piece 2 down onto piece 1 does not work due to the tapered nature of the cut.
With the thicker #3 blade the joints become that much sloppier and the puzzle has less cohesion as a whole, although a few pieces in a shaped frame can negate this effect once assembled.
The only other 3D puzzles are really 2D puzzles that stand upright. Again these are cut from thick timber and need to be cut carefully to retain cohesion. There are a series of interlocking animals (the bass is the most famous) that patterns are also available for but again these are more toys than puzzles in the traditional sense of the jigsaw puzzle.
Items such as Grandpa's wonder puzzle and interlocking puzzles are also cuttable with the scrollsaw, there is a fanatical following to these in some areas of the web as much for the mathmatical solutions underlying them as the elegance of the puzzles, but they can be very difficult to cut accurately for the more complex ones.
HTH,
Steve.