I always double check battery replacements before buying items for this reason. It is hard to predict what sizes will stick around, but I am also not against busting a device open and fitting a near-enough sized cell with the right output.
As a plus you can pick them up in e-cigarette shops, apparently vape units use them too.
Often you can get them with leads/connector pre-soldered (which is good for hobby electronics since you don't really want to be soldering straight to a lithium battery and not all electronics already have a cradle)
Any hints how to solder it better?
Another tip is to use plumbers flux and an old soldering bit to 'tin' the battery first, the solder will fairly leap onto it with such flux. :) Don't forget to clean the flux residue off as it's quite corrosive.