There are lots of threads on the strap bit, but as usual the answer is it depends

Some stores will let you order a strap at any time; some only twice a year; some have a stock of straps (rare). My craftsperson told me a strap would not take long but I have had other stores tell me more than a year to wait. Often it just depends on whether they like your bag!!
Also depending upon the store they may take your bag for a while to ensure a match - this depends as Birkel said upon age, colour, fading, etc.
Locks I am not certain about but they can certainly be found at resale.