I bought almost all of them with cash from an ATM at < 1000e.
Then that's what you'll tell your bank. You weren't required to keep an administration, so you didn't keep any records. You're not the only one who did this.
My understanding is that a traditional bank will frown at this to say the least.
They'll send you a letter. And you'll have to answer the questions. If they refuse, they'll close your bank account.
What are my options? Does anyone have any experience on how to go about this in a legitimate way?
The only legitimate way is to come clean. Face the music.
If bank, what kind of proof do they need in this case?
My interpretation of what banks are doing: they've had massive AML-fines, and had to hire thousands of people to go through their customers' personal transactions. Government doesn't even tell them what they want, they just tell them it's their job now. So banks don't take any risk, ask way more than they need just to be sure, and report anything suspicious to government. Government gets overloaded with reports, and has no idea what to do with them.
Banks are just trying to cover their asses, and want to do that as thorough as possible.
How to go about 'proving ownership' or what is the procedure both with the bank and the tax folks?
For the bank, signing a message from an old address may work. For taxes, see below.
I reside in a country where there is a high chance that no capital gains taxes are charged, however I'm not trying to evade taxes or anything of the sort.
There's no capital gains tax, but there's a capital tax. Assuming you're above the threshold, you're required to report your wealth and pay taxes annually. If you haven't paid yet, they'll still charge you once you report it (and if they find out on their own it's going to be more expensive).
I reside in the Netherlands.
Me too.
KYC isn't the thing to worry about: your bank already knows who you are. I think it's actually worse if you use a shady non-KYC exchange to transfer 30k to your bank account. I'd start with Bitonic, the oldest Bitcoin broker in the country.
Using a mixer in between makes it harder to prove capital gains, it would help if you find back all original addresses so you can prove where you started. The reason to prove wealth came from Bitcoin's price increase, is because the alternative would be it came from crime. If you suddenly show up with a million euro in Bitcoin, you're going to need a good story to explain it.