If you are certain that somehow the data file was not changed (e.g., reduced) in between runs, it sounds that there is no robust, stable factor structure. If I were you, I would stick with a full sample EFA, and report that its results are tentative and purely exploratory. In a footnote or discussion/limitations, you could explain why the reported factor structure might not be replicable.

Hi, Evren. There are some assumptions that your data set should meet so as to be able to run EFA, meaning that we cannot do EFA cursorily on any sets of data. First, it is the issue of sample size. I suggest retaining your full sample size since it is one of the main issues you need to consider in EFA. Another one is the strength of the relationship among the items. Clearly, your items should show some correlations (at least .3) with each other. You can check them by Bartlett’s test of sphericity and the KaiserMeyer-Olkin (KMO) measure which can be found in the output of EFA on SPSS. Other assumptions are linearity and not having significant outliers. By the way, for your factor extraction, there are three common ways, namely Kaiser’s criterion (eigenvalue rule), Catell’s scree test, and Horn’s parallel analysis. I recommend checking all three ways to see and make sure that how many factors you have to extract in the EFA phase. Moreover, you can try different approaches (orthogonal or oblique) and techniques (varimax, quartimax, equamax, direct oblimin, or promax), albeit with regard to their rationale and logic, to find the appropriate number of factors that you need to extract.