Wow, we had EXACTLY the same experience.

A lengthy process (about 3 months) to get signed up with Sage Pay only to be declined the merchant account (yet to give us a reason although they said they would tell us, that was 2 months ago).

We ended up settling on PayPal just to get started, not ideal for taking recurring payments, but quick, easy and better than nothing.