The experienced jigsaw player uses several clues to speed the solving rate.

In particular, finding edges and corners can greatly increase the rate of progress, since to a first approximation it divides one large pile with n*(n-1)/2 piece combinations into two piles, with m*(m-1)/2+(n-m)*(n-m-1) combinations.
For example, for a 1,200 piece (40 by 30) jigsaw there are naively 1200*1199/2=719,400 piece combinations, whereas if pieces are sorted into sides and centres there are 40*2+(30-1)*2=138 sides (and corners), with a mere 9,453 combinations which can be performed first, leaving a sub-puzzle with only 563,391 piece combinations.
The centre would then generally be solved by attempting to divide-and-conquor in other ways, such as comparing pieces with similar overall colour or other obvious details.

Clearly, these practices must be stamped out. Therefore the maximal difficulty jigsaw attempts to confound these expectations:
* The edges of the jigsaw also carry knobbles.
* The shape of the jigsaw as a whole is not rectangular.
* The pieces are not designed to a regular grid.
* The image used is carefully chosen not to have any large, easily distinguishable areas.
* A fraction of the pieces do not have a knobble on one side - these are usually (but not always) internal.
* Where possible, piece edges follow significant boundaries of the image, and 'obvious' details are entirely contained within a piece.

Research in the jigsaw labs appears to be leading to "silly putty" pieces, that not only have flexible shapes, but can have their image shifted as well.

For Loris: a gift - the un-jigsawed Puzzle.
It consists of perfectly square featureless black tiles. These tiles have no obvious orientation, even front and back. Internally, they contain RFID chips and sufficient circuitry to identify their neighbors. When queried, each chip will report whether it has the appropriate neighbor on each of its sides (or no neighbor, if *that* is appropriate to the tile). A scanner queries each of the tiles, and if they all are correct, the scanner beeps, blinks a green LED, says "Yes", or other congratulatory message. Any other configuration says "No", so you get only a single bit of information from each arrangement attempted.

As you lay out the n tiles, there are n! orders to lay them in (I will grant that you know the finished dimensions in advance, such as square, or 1*n, or whatever), and there are 8 different orientations in which each piece can be laid. Therefore, there are 8^n combinations of orientations, yielding 8 possible orientations for the final completed puzzle. So your chance of getting it right are 1 in n!(8^(n-1)).

For Loris, I think the 4x4 piece puzzle should suffice: your odds are around 1 in 7.4x10^26.

There was a puzzle back in the '90s that was billed as 'the
world's most difficult' jigsaw puzzle; it was a big red circle
with about 2000 pieces or something, and a number of
them were nearly identical in shape. I remember thinking
that a puzzle with no discernable edges would be even
more difficult.

I should say that the idea is not to make the puzzle practically impossible, but rather to challenge jigsaw enthusiasts in an interesting way. There still would be logical clues available to make the problem solvable, just not the immediate ones they're used to.

[lurch] The puzzle you described is not, in fact, the
most difficult possible jigsaw. The minimum-
information jigsaw would be like yours, except the
user wouldn't know the value of "n" (total number of
pieces) beforehand.

I've heard of edgeless puzzles with a few superfluous pieces
thrown in. Diabolical! I've also seen puzzles where there
are no edges and every piece is the identical shape with
the only clues being the image which is usually something
like a mass of earthworms or such.

There are existing puzzles with (IIRC):
No edge or corner pieces
Repetitive image (see linky)
A few extra pieces (as per [AusCan531])
The same image printed on the back of the pieces (rotated 90 degrees I think)

There's also the Wasgij, in which the image on the box is not (but is related to) the image on the puzzle.
Not a grid-pattern or rectangular would be good and tricky.

Cockroach jigsaw puzzle: if you don't finish it in one
sitting, all of the loose pieces crawl away and hide under
the fridge. At night, they come out and assemble
themselves on the kitchen floor, but they scatter when you
turn on the light.

//no edge pieces...// One way to guarantee that you never finish the puzzle - every month you receive, in the mail, an envelope containing a few more pieces which expand the puzzle just a bit.