I'm working on a cross-country study where I look at the impact of different regulatory variables on bank stability (so the dependent variable is at the country-bank-year level and the variable of interest is at the country-year level).
Your banks are nested within countries, but the regulatory variables of interest are at the country level. Regulation more than likely impacts all banks within that particular region/country. And, the within-country errors are likely not independent of each other. This supports clustering at the country level.
My data set is an unbalanced panel which consists of 5000 banks operating in 39 countries over 2000-2015.
Cluster-robust uncertainty estimators perform poorly with scanty clusters. In your case, 39 is getting a little low in my estimation. Applied research in this area suggests anything north of 40 is sufficient for the cluster variance formula to be accurate. Chapter 8 of Mostly Harmless Econometrics by Angrist and Pische (2009) offers a thorough appraisal of clustering issues and serial correlation in panel data models. You could also check out their blog.
Here is a quote from Cameron and Miller's practitioner's guide to cluster-robust inference on page 3:
There is no clear-cut definition of “few”; depending on the situation “few” may range from less than 20 to less than 50 clusters in the balanced case.
I would review some of the finite sample corrections recommended in this guide. And, I would venture to say anything below 50 clusters (definitely 40) is cause for concern.
However, a few people suggested to me that since my variable of interest is at the country level, I should cluster standard errors at the country level. When I did that, the level of significance of my variable of interest drops to 10%.
I agree with this advice. You're primarily interested in regulation instituted at the country level—so cluster there. In general, uncertainty estimates will be more conservative if you cluster at this higher level. Review this post for more information.
I would also avoid obsessing over "significance" in applied work. Recent scholarship is exhorting researchers to eschew the dichotomization of p-values. It puts you in a position where you're fishing for significant results. I would try out a couple of different uncertainty estimators (clustering at the country level), maybe even a pairs cluster bootstrap approach, and see if your results change.
Again, 39 clusters ins't big and it isn't small. I doubt anyone will fault you for attempting other finite-cluster corrections. I think others on this forum will agree with a country clustering scheme. If there is any disagreement then I am sure others will offer their input.
I hope this helps!