How scared should we be about convergence warnings in lme4 If we a re fitting a glmer we may get a warning that tells us the model is finding a hard time to converge...e.g.
>Warning message:
In checkConv(attr(opt, "derivs"), opt$par, ctrl = control$checkConv,  :
  Model failed to converge with max|grad| = 0.00389462 (tol = 0.001)

another way to check convergence discussed in this thread by @Ben Bolker is:
 relgrad <- with(model@optinfo$derivs,solve(Hessian,gradient))
 max(abs(relgrad))
 #[1] 1.152891e-05

if max(abs(relgrad)) is <0.001 then things might be ok... so in this case we have conflicting results? How should we choose between methods and feel safe with our model fits?
On the other hand when we get more extreme values like:
>Warning message:
In checkConv(attr(opt, "derivs"), opt$par, ctrl = control$checkConv,  :
  Model failed to converge with max|grad| = 35.5352 (tol = 0.001)

relgrad <- with(model@optinfo$derivs,solve(Hessian,gradient))
max(abs(relgrad))
#[1] 0.002776518

Does this mean we have to ignore the model results/estimates/p-values? Is 0.0027 far too large to proceed? 
When different optimisers give different results and centering of variables / removing parameters (stripping models down to the minimum) does not help but VIFs are low, models not overdispersed, and models results make logical sense based on a priori expectations, it seems hard to know what to do.
Advice on how to interpret the convergence problems, how extreme they need be to really get us worried and possible ways to try manage them beyond those mentioned would be very helpful.
Using:
    R version 3.1.0 (2014-04-10) and lme4_1.1-6
 A: I just want to supplement @Placidia's great answer. You may want to check out "Richly Parameterized Linear Models: Additive, Time Series, and Spatial Models Using Random Effects" by James Hodges (2014). It discuses what we do not know about mixed models and at the same time attempts to offer a broad theory as well as practical tips for fitting complex models.
An often scared modeler myself, I find Hodge's discussions of "puzzles" priceless. He explains strange cases arising from fitting mixed-effects modeling, including "A random effect competing with a fixed effect" and "Competition between Random Effects". Sounds familiar? 
A: Be afraid. Be very afraid. 
Last year, I interviewed John Nash, the author of optim and optimx, for an article on IBM's DeveloperWorks site. We talked about how optimizers work and why they fail when they fail. He seemed to take it for granted that they often do. That's why the diagnostics are included in the package. He also thought that you need to "understand your problem", and understand your data. All of which means that warnings should be taken seriously, and are an invitation to look at your data in other ways.
Typically, an optimizer stops searching when it can no longer improve the loss function by a meaningful amount. It doesn't know where to go next, basically. If the gradient of the loss function is not zero at that point, you haven't reached an extremum of any kind. If the Hessian is not positive, but the gradient is zero, you haven't found a minimum, but possibly, you did find a maximum or saddle point. Depending on the optimizer, though, results about the Hessian might not be supplied. In Optimx, if you want the KKT conditions evaluated, you have to ask for them -- they are not evaluated by default. (These conditions look at the gradient and Hessian to see if you really have a minimum.)
The problem with mixed models is that the variance estimates for the random effects are constrained to be positive, thus placing a boundary within the optimization region. But suppose a particular random effect is not really needed in your model -- i.e. the variance of the random effect is 0. Your optimizer will head into that boundary,be unable to proceed, and stop with a non-zero gradient. If removing that random effect improved convergence, you will know that was the problem. 
As an aside, note that asymptotic maximum likelihood theory assumes the MLE is found in an interior point (i.e. not on the boundary of licit parameter values) - so likelihood ratio tests for variance components may not work when indeed the null hypothesis of zero variance is true. Testing can be done using simulation tests, as implemented in package RLRsim.
To me, I suspect that optimizers run into problems when there is too little data for the number of parameters, or the proposed model is really not suitable. Think glass slipper and ugly step-sister: you can't shoehorn your data into the model, no matter how hard you try, and something has to give.
Even if the data happen to fit the model, they may not have the power to estimate all the parameters. A funny thing happened to me along those lines. I simulated some mixed models to answer a question about what happens if you don't allow the random effects to be correlated when fitting a mixed effects model. I simulated data with a strong correlation between the two random effects, then fit the model both ways with lmer: positing 0 correlations and free correlations. The correlation model fit better than the uncorrelated model, but interestingly, in 1000 simulations, I had 13 errors when fitting the true model and 0 errors when fitting the simpler model. I don't fully understand why this happened (and I repeated the sims to similar results). I suspect that the correlation parameter is fairly useless and the optimizer can't find the value (because it doesn't matter).
You asked about what to do when different optimizers give different results. John and I discussed this point. Some optimizers, in his opinion, are just not that good! And all of them have points of weakness -- i.e., data sets that will cause them to fail. This is why he wrote optimx, which includes a variety of optimizers. You can run several on the same data set.
If two optimizers give the same parameters, but different diagnostics -- and those parameters make real world sense -- then I would be inclined to trust the parameter values. The difficulty could lie with the diagnostics, which are not fool-proof. If you have not explicitly supplied the gradient function and/or Hessian matrix, the optimizer will need to estimate these from the loss function and the data, which is just something else that can go wrong.
If you are getting different parameter values as well, then you might want to try different starting values and see what happens then. Some optimizers and some problems are very sensitive to the starting values. You want to be starting in the ball park.
