Specifying a (simple?) two level model

Your first model is asking too much. You are estimating 22 variance
components and (22*21)/2 correlation parameters for them.
Your second model is a good start for your question. Here is what the
model returns for you:

ranef(my.fit)

This values are what Douglas Bates prefers to call "the conditional
modes of the random effects". To quote him: "If you want to be
precise, these are the conditional modes of the random effects B given
Y = y, evaluated at the parameter estimates."

Basically, they give you relative positions of countries and clusters
to the intercept, taking into account the reliability (i.e., n of
observations) you have for the other factors levels. So adding the
terms yields a "prediction" on the basis of the two random factors.
     This model does not give you country-specifc effects. One way to
model the interaction is to assume  that there is a random effect for
each county and a separate random effect for each combination of
country and employment history.  If the random effects for these
combinations are assumed to be independent with constant variance,
then the following model is appropriate:

m2 <- glmer(poverty.third.year ~ 1 + cluster + (1 | country) + (1 |
country:cluster), family = binomial("logit"), data = poverty.risks)
This model still generates 499 conditional modes, but uses only 2
variance components plus residual variance plus 21 fixed effects for
clusters. This may be a good compromise or at least starting point.
It completed in about 20 minutes on my machine.