You are very wise to research this before moving. I homeschooled in the US, then moved to Europe and ended up in Sweden just as the new ridiculous law was passed, and it was truly like a nightmare to no longer be able to homeschool without breaking the law. We've been here for two years and luckily my son is well adjusted and there is no 'major' issue with school, but he's bored and I can tell his talents are being wasted. We're slowly working our way out of here, probably back to the US for financial reasons. We'd love to go to the UK so we can eventually work our way further south in Europe, but having a non EEA spouse makes it a little insecure.
As far as Spain and HS being illegal--I thought Catalonia made it legal recently. As for HS in the past in Spain, it's always been difficult. I think most people are doing and have been doing it under the radar. But there are definitely tales of court cases etc.
I don't know about Austria, Switzerland, Poland and Italy much. I know it's difficult in Italy, but people do do it there. It's supposedly easier if you're a foreigner. Look up national HS networks, there are blogs out there too, ask around.