It turns out that the orientation of the cutlets is enough to define the entire state. This is also true of the 3x3x3 cube. Each one can have one of 24 orientations, and the position can be determined by the orientation. To prove to yourself that this is true, consider a completed cube centered at the origin and define each pieces geometry in world coordinates. All cube manipulations consist of rotations around one of the 3 axis, there are no translations. There are 24 orientations possible.

Given that, the 2x2x2 cube can be encoded as 8 orientations with 24 value for each. This results in a maximum of 24^8 cube positions or about 100 billion, many of which are not actually valid. So one could start with the solved cube and do a breadth first exploration of the entire space. You'd scan an array of 100B positions for any one that has a known solution (the complete cube is initially the only one). For each position with a known solution, make all possible moves from there and record the move required to solve the cube at any new positions reached. Repeat until no new positions can be reached.

Someone said the 2x2x2 cube can always be solved in 11 moves or less, so 11 scans across a 100B possible positions will be sufficient to create a database of optimal moves to solve from any position. This should be reasonable to do.

As I think about this, on the small cube turning one face has the same effect as turning the opposite one the other direction. So we could start by picking one corner and turn the entire cube so that corner is in final position. From that point, only 4 faces could be turned either CW or CCW, so encoding a move would require 3 or 4 bits, and there would be 1/24 as many positions because the one cubelet is not movable. This would be about 4-5 billions positions which would fit in RAM on a lot of modern laptops or a DVD.

I had expected something like this knowing that it's impossible to solve a 3x3x3 after assembling it with a corner rotated incorrectly. Thanks for this insight!