I feel your pain re Realex fees, but they do a lot as far as transferring funds to your bank account nightly, and generally being incredibly transparent about their fees. I wouldn't recommend any of my clients to use anyone else, and WorldPay told me before that they weren't willing to take very small accounts at the time, which my client had (it really wasn't worth while for anyone to take them on at all).
None the less, Realex are always professional, and once you give them accurate information, they will generally help you out very quickly. Doubt they rejected your custom on that basis Irish Millionaire, as they are always expanding their team, is it possible your bank wasn't willing to give you a site merchant ID - this can happen unless you blurb a huge document about your sites design, development, structure and SSL certificates, etc...
Paypal is easiest for small quantities of sales (Under €500 a month)