- Does Bob have a case/standing?
Yes, this is a reasonably straightforward contract dispute. Once you contract to do something and you then don't do it, you are liable for damages. Contractual damages are assessed on an expectation basis - the innocent party is entitled to be placed financially in the same position as though the contract had been completed without the breach. Bob is entitled to have the item and not to be out-of-pocket more than he agreed to pay.
But ...
There may not be a contract - see What is a contract and what is required for them to be valid?
A contract is formed when the parties reach an agreement and most website terms and conditions are clear that this is NOT when the customer pays for it. For example, Amazon says:
The Order Confirmation E-mail is acknowledgement that we have received your order, and does not confirm acceptance of your offer to buy the product(s) ordered. We only accept your offer, and conclude the contract of sale for a product ordered by you, when we dispatch the product to you and send e-mail confirmation to you that we've dispatched the product to you (the "Dispatch Confirmation E-mail").
So, here, two things have to happen before Amazon and you have a contract: they have to physically dispatch the goods and they have to send you an email saying they have. If they do one without the other, there is no contract. If your vendor has similar terms, you don't have a contract with them and are not entitled to contractual damages.
You would not have a case in equity because they were clear that there was no contract until these things happened.
You might be able to argue negligence if they sent the email without dispatching the goods but your damage basis would be different. Tort damage is calculated on a restoration basis, not an expectation basis, so you can recoup your losses but not claim any lost profits. It makes no difference here but if you had had a buyer who was going to pay you twice the price you paid, in contract you are entitled to the lost profit, in tort, you aren't.
However, if the contract has a dispute resolution clause, that would normally have to be complied with before you can go to court. In some cases, this may prevent going to court at all, for example, if the dispute resolution clause included binding arbitration or expert determination.
If there is a choice of law clause then this will usually be binding, however, if this is a consumer contract in New Zealand then NZ consumer law will apply in addition.
Similarly, courts will usually observe a choice of venue clause.
With what reasonable time lapse between (false) shipment notification of the original order and placing the eBay order?
A reasonable time. Depends on what the product is and what normal delivery times are. For a 5mm screw, a reasonable time is probably measured in months. For an aircraft carrier it's probably measured in decades.
- Does this sort of a claim fall under the jurisdiction of small claims court (given that the amount is less than the threshold)?
Neither New Zealand nor England & Wales (bearing in mind Scotland and Northern Ireland are different jurisdictions) have small claims courts.
The correct venue in New Zealand is the Disputes Tribunal which is not a court, and in England and Wales it is the County Court.
Procedurally, would it be more advantageous for Bob to file the claim in the UK or in New Zealand?
Ask a lawyer in each jurisdiction.
Now Bob wants to claim damages from the store in the amount "Total for the eBay order less total for the original store order" — on top of full refund of the original order.
Bob is not entitled to a refund. He is entitled to damages. A more accurate way to state the damages is the total for the eBay order and to not make any mention of a refund.