I nailed this UHV some time ago. Because I'm running the Protestantism modcomp and the fixed Arabian UHV (destroy all non-state religions from conquered cities) on my RFC, I couldn't be the master of all Christianity, Judaism and Islam. Judaism was replaced by Protestantism and in my game (3000 BC start) India was very strong. I couldn't capture Delhi either so what did I do? Change state religion from Islam to Catholic Christianity just turns before researching Printing Press, after which All Saints' Church auto-constructed itself on my capital, Mecca.

I guess I could have conquered Delhi while I was at it, but from what history has taught me wars with two fronts are to be avoided at all costs. And since I was already expanding West (taking Persian and Mesopotamian lands under my wing before doing so), I would have taken a too big risk. Instead, I figured I could control the monotheistic faiths even if I had lost Judaism. Mecca was then home to both Islam and Protestant Christianity while Al-Quds (Jerusalem) was the home to the Catholic faith.
In my opinion Spain was actually pretty easy to conquer. Just bring along a few Cannon (beeline for Gunpowder), remember to build the Suez canal with a fort, construct a few Galleys and just ship your troops there. Carthage (Qartaj after capture, Tunis if founded) acts as a fine port city to leave your troops by right before the inevitable attack to Iberia. In my game I first captured Valencia, then rushed to Madrid and finally took over Sevilla. By now, the Spanish had collapsed. When 1300 AD came by, I had already lost Madrid and Sevilla to the Spanish Independents (Reconquista!) and I only had Sevilla occupied, but apparently that was enough.

Qartaj and Valencia was soon then after gifted to Portugal, which then converted to Islamic faith and captured Madrid and Sevilla back as members under one Iberian coalition. My next step was to attack to Greece and from there Islamisize all of Europe. I got bored and faced too much opposition after conquering Greece and Italy in whole, after which I attacked to India's poorly defended Tashashila, a very big city. After this, Islam had already reached 40% of world's population.
I'm guessing you don't run either modcomp, Protestantism or UP fix, but I can say the thing to remember is that you have to keep the West under constant pressure and remember that RFC's Arabia is based solely around religion. The Spiral Minaret and University of Sankore are two must-wonders that you have to build and your economy is to be based around the Shrine income and the bonus from building Spiral Minaret. Learn to use religion to your advantage and you'll notice that even Arabian UHV can be nailed succesfully.