Find the smallest square with your search point at the center and exactly one other point inside that rectangle (you need to do logn number of searches).
Let x be the distance to the other point.
Then find all the points within a square whose side is 2x and centered around your first point. For each point within this square, calculate the distance from search point and find the closest.
UPDATE: How to find one square centered around search point that contains exactly one other point?
Find a random point. Let the distance to that random point be x. Find all points within square of size x centered around search point. If there are non zero number of points within this square, then select a point at random and repeat. If there are no points, increase search square size to (2-0.5)*x (in next step (2-0.25)*x and so on.