Some hints for solving this problem the way I was able to solve it, without greedy search

1. I used BFS search with heuristic (A* search). As a heuristic, I used the sum of the distances from the boxes to the nearest goals, taking into account that different boxes should be on different goals. It is better to distribute boxes among goals in some greedy way, so as not to spend a lot of time on this.
2. In the board states, DO NOT store the position of the player, store the places he can REACH. This will greatly reduce the number of states needed to be stored. You can store one board state in two 64-bit numbers as bit masks.
3. To find bad positions and stop further search on them, look for simple deadlocks (the box is in a corner and not on a target), dynamic deadlocks (the boxes block each other) and NOT COMPLEX corral deadlocks (the boxes are not on goals and block access to some board area, so they cannot be pushed out of there).
4. If you try to search for too complex corral deadlocks, the time spent on finding them will not be worth it. Try different settings of what difficulty of corral deadlocks to search for and when to stop the search. Store the found configurations of corral deadlocks (and the configurations in which no deadlock was found) in some sets so as not to determine them every time.
5. In addition to the forward search (pushing boxes from the starting positions to the goals), you can also use the backward search (pulling boxes from the goals to the starting positions) to reduce the depth of the search tree.
6. For the forward (backward) search, prevent situations when, for example, there are more (fewer) boxes near the wall than goals. This can greatly speed up the search for some boards.
7. To understand why your algorithm is working too long for a particular board, you can find and output long deadlock branches - a sequence of pushes/pulls in the search tree that starts from one of the board states that is in the found solution and that does not eventually lead to the solution. This way you can find bugs when the algorithm did not find one of the types of deadlocks and did not stop searching on them.

Good luck!