http://cs.ulb.ac.be/~fservais/rushhour/ has a listing of puzzles that take the most moves, but also mentions how many different configurations are possible.
The guy who made the website literally wrote his master's about it: http://code.ulb.ac.be/dbfiles/Ser2005mastersthesis.pdf