Point Pattern Recognition
From a computer vision perspective: the basic problem is estimating a homography between your target point set and a subset of points in the large set. In your case, with rotation only, it will be an affine homography. You should look into the RANSAC method. It is designed to find a match in a set with many outliers.  So, you are armed with two important keywords, homography and RANSAC. 

OpenCV offers tools for computing these solutions, but you can also use MATLAB. Here is a RANSAC example using OpenCV. And another complete implementation.

A typical application might be to find a book cover in a picture.  You have a picture of the book cover, and a photo of the book on a table.  The approach is not to do template matching, but to find salient corners in each image, and compare those point sets.  Your problem looks like the second half of this process - finding the point set in a big cloud. RANSAC was designed to do this robustly.



I guess cross-correlation methods can also work for you since the data is so clean. The problem is, you add another degree of freedom with rotation, and the method becomes very slow.