I'm employed in Portugal without a (completed) CS degree, and I had more than one company to choose from. From what I could tell, the interviews were much more important than any lines on my CV.

I'm actually Portuguese, the only people I know that managed to do that, were guys and girls from my degree doing something on the side during the .com days for some startups, back in the 90's.

Never saw that in the big companies, but it's been several years that I don't work there.

Well, the only "big" company I interviewed for was Sybase, but they were interested (although, I think they mentioned that my salary would be affected by that).

I chose a smaller software company, though. I much rather earn less but have a less enterprise-y work environment.

Personally I'd regard any company where the HR department gets to filter candidates on silly criteria like that as somewhere I'd never want to work.