Here is a grid which does not contain a puzzle with 16 clues:

937856241

562194387

481273569

823647915

615932478

749581623

378469152

196725834

254318796

How do I know? By a computer calculation.

Recall that an unavoidable set is a set of cells such that the digits in the cells can be permuted to obtain another valid sudoku grid.

Any set of clues for a sudoku puzzle must include a clue from any unavoidable set.

First find the following unavoidable sets in this grid:

{17,19,77,79} (17 means row 1, column 7, etc)

{27,28,87,88}

{37,39,47,49}

{41,43,71,73}

{44,45,74,75}

{11,21,15,25}

{23,33,24,34}

{53,63,54,64}

{81,91,85,95}

{83,93,89,99}

{55,65,59,69}

{42,52,46,56,48,58}

{94,96,14,12,36,32}

{82,92,76,86,98,78}

{16,18,22,26,31,38,51,57,62,67}

Next observe that any two of these sets are disjoint (have no elements in common).

There are 15 sets, so we know already that any puzzle from this grid must have at least 15 clues.

With a friend who is a far better programmer than me, we wrote a program to find all possible choices of 16 clues with one from each of these unavoidable sets. We also included other unavoidable sets, and we ensured that the choice of clues included one from all these sets.

The result was about 1e8 possible puzzles with 16 clues.

We ran each of these through a solver written by dukuso (many thanks) and every one had multiple solutions. Total computation time: about 20 hours on 2.1 GHz.

Barring bugs, this grid has no 16.