The need to prove a negative arises only from the way you've phrased the problem.
In the UK, theft is defined as—
- dishonestly
- appropriating
- property
- belonging to another
- with the intention of permanently depriving its legitimate owner of it.
All five elements must be proved in order to secure a conviction for theft.
In the case of an item removed from a store, the prosecution must prove beyond a reasonable doubt that—
- the defendant had a dishonest intent;
- the defendant appropriated the item (treated it as his own);
- the item was 'property' (straightforward in this case);
- the item belonged to someone else (ditto); and
- the defendant intended to permanently deprive the owner of it.
Clearly proving that the defendant left the shop without paying would be an important element in proving (2) and (5) above. Note that the prosecution must prove that he left without paying, not that he did not pay. In this example, the prosecution might adduce CCTV or witness evidence of defendant leaving without paying.
If the defendant did pay for the item but doesn't have a receipt, he can still give witness testimony in his own defence. The prosecution is unlikely to have strong evidence to the contrary if payment was in fact made. The totality of evidence, put before a jury or summary court, will be considered in the round when establishing guilt.