Wrote this up in response to the renewed attention to the problem:

17x17 is NP-Complete: http://hackerne.ws/item?id=3584732