Actually they tried.
We have records that already in the mid-12th C. Muslim navigators from al-Andalus were making expeditions down the West African coast, trying to reach the Senegal and Guinea coast by sea, circumventing Almohad-dominated Morocco.
However, it will be noticed that the timing of these expeditions falls within the "second taifa" period, when al-Andalus and Morocco were under different rulers, a situation which ended when the Almohads finally crossed over to Spain.
So Christian powers did not add too much to this equation, other than being almost permanently inimical to Morocco. That said, blockades of access to the trans-Saharan and eastern trade was a political thing more than a religious one. Christian Genoese and Majorcan merchants had no problems, and enjoyed quarters in Muslim Moroccan and Granadan cities, much liked they did in Christian Lisbon and Seville.
The Italian factor should not be underestimated. They were the prime movers of the Atlantic exploration business - they brought in the capital and the expertise, both commercial and technical. And they were not particularly attached to anybody. They were as willing to go with Portugal as with Castile or Granada or Morocco.
The Genoese rivalry was not so much with Muslim powers, but with Venice, who had acquired a near-monopoly position in the eastern Mediterranean by virtue of its privileged relationship with Mameluke Egypt, and shut them out. The Genoese had bet on the Il Khanate and later the Timurids, but those states failed and the Ottomans were not nearly as amenable. It is really only after Kaffa and Constantinople fell when they turned to the western route. And they were not picky. Genoese and Pisan-Florentine expatriates pushed the courts of Portugal, Castile and Granada and Morocco for it. Only Portugal took them up, and merely because of the peculiar personality of its king, himself a merchant by instinct, with commercial experience while a young prince, who "got" what they were talking about. None of it was necessarily predicated on the reconquista happening or not happening. You just needed a greedy ruler willing to serve as sponsor.
(You will notice that in Columbus's case, the prime movers behind the scenes were not Castilian officials of pious Isabella, but Aragonese officials of machiavellan Ferdinand II, like Luis de Santangel. Even though the Columbus enterprise was all done in the name of Castile, and Aragon was theoretically out of it, the high levels of it was pushed and handled by Fred's men. It is only when Bishop Fonseca came on the scene that things changed.)
Marinid-Wattasid Morocco was too much in the throes of political anarchy throughout the 15th C. to theoretically have done it. Fez did not control the Moroccan coastal ports - they were in the hands of quasi-independent local governors and self-proclaimed maritime/corsair republics. And (by the 15th C.) Morocco lost its coastal ports altogether to Christian powers (Portugal & Castile again). This, more than anything, precluded it from being able to do anything by sea, even if they could be persuaded.
That said, keep in mind also that Morocco didn't really have too many Atlantic ports - with a few exceptions (e.g. Tangier, Sale), most were all new constructions. The traditional ports were on the Mediterranean coast side (Ceuta, Mellila, Nakur, Oran), not the Atlantic coast side.
But a non-reconquistated Spain would have been a different story. Just from what we know, al-Andalus had several major Atlantic ports - Lisbon, Alcacer do Sal, Silves, Faro, Tavira, Huelva, Seville, Cadiz, etc. some with working arsenals and experienced fleets, to which can be added the maritime expertise of Algeciras, Malaga, Almeria, Cartagena, Denia, Valencia, and, of course, Majorca, on the other side. That's quite a list.
We know at least that the Andalusian ships - fishermen, corsairs and/or merchants - from Lisbon, Alcacer, Tavira, Cadiz and Seville had been relatively active - indeed, it is probable that they were quite aware of Atlantic islands. At least we see that suggested in tales of Medieval Andalusian mariners, e.g. the "Eight Maghurin" of Muslim Lisbon and the navigator Khashkhash of Cordoba. So the naval resources were there. It is simply a matter of motivation and capital.
Motivation would be afforded by any conflict between al-Andalus and Morocco - and there was plenty of reason and occasions for that, indeed it was almost certain to happen. They were constantly at odds in their day, intervening time and again in each other's affairs, setting up puppets and pretenders against the other. The few times there was concordance accross the straits was when one side or the other was fragmented and weak and the other could "impose" itself. In the 10th C., Andalusians had the advantage, in the 11th-12th, Moroccans had the advantage.
All this depends on exactly what you mean by "no reconquista". No success at all? A little success, but not complete? Stalemated at what date?
The reason it is important to ask is, of course, the reconquista was a major factor in weakening al-Andalus, and making it susceptible and dependent on Morocco. But Morocco had its own other fronts to fight - on the southern Sahara and in the eastern Algerian front - which never allowed it to focus full attention on Spain. The greatest gains of reconquista were done precisely when the Moroccans were too busy elsewhere and left it up to the Andalusian cities to save themselves.
So if there were no taifa periods, or if the Christian powers were unable to exploit them, and al-Andalus emerged if not entirely united at least under a couple of great powers (say, a Sevillan-centered west, a Granada-centered south and a Valencia-centered east - just to mirror the Portugal-Castile-Aragon in the north), then the story could play out differently. In this situation, Morocco, would be merely a background player, a looming potential threat to the Andalusian states, occasionally lending support and mercs to one kingdom or the other, but unable to dominate, and usually rivalrous and excluded from the peninsula (much like France was to Christian Spain)
In such a configuration, I don't see a reason why Genoese entrepreneurs couldn't persuade the emir of Seville to make a direct sea route to Guinea gold and later a sea route east.
The only question which remains is the reconquista frontierland. Whether the Douro valley or the Tagus valley, there would be an emptied space between them, which would be a scene of continuous cross-raids but otherwise empty. It might seem "inconceivable" to allow such fertile land to remain unused. But it is not so inconceivable - as we saw in the Hapsburg-Ottoman frontier on the Balkans. It could remain no-man's land for a spell, and only gradually populated later as kingdoms congealed.
As for European crusades, mm, don't see that. Remember that during the height of the Crusades, all of al-Andalus was still in Muslim hands. Outside a couple of Crusader ventures (Lisbon, Silves), other European powers were a non-factor in Hispania. Not sure why it would be any different than it was.
