Li-Ion batteries need a bit of conditioning before they'll hold their optimum charge.

When I select the "deep discharge" function on my camera, it drains the batteries right down - possibly below the level at which the camera would cease operating.

Some phones have this function, some don't. If you don't have the function, the next best thing you can do is let it go right flat. Preferably whilst using it. Play the games on it or just twiddle the menus around when the battery level is reportedly "omfg!rechargemeNOW".