For printing, you're better off at 250 DPI (dots per inch or above). The more you go above this number, the better your print. The more you drop below it, the more evident things like pixelation, gradients etc appear.
A4 on it's longest side is 29.7cm - lets call it 30 cm, which is 12inches. At 250 DPI, that means the longest side on your shot should be at least 3000 pixels. Anything smaller than that and you're dropping the DPI.
People can cheat and simply upsize shots, but doing so incorrectly or badly will/can degrade your print. So if you're looking for high resolution images that are to be printed on A4, ideally they should be 3000 pixels on the longest side, or greater.
If Photobox is quoting 1600.. those prints will be a disgracefully low 133 DPI