Yeah it's no problem. They may have to order them for you, but they should be able to do that. My bike came built with the wrong sized crankarms for the frame size, and the shop just ordered a pair in the right size and installed them. Then they dealt with the bike manufacturer about getting reimbursed (because the bike was sent to the shop with the wrong parts).

You don't even have to go with Shimano if you don't want to. I believe FSA crankarms are compatible. Maybe you'd need an FSA spider too, but your current Shimano BB and rings will definitely work. Of course, FSA will probably be more expensive, especially if you go with carbon. With a 105 crankset, I wouldn't really worry about upgrading parts of it. Either keep it the same and save cash or upgrade the whole thing. I just rode a new 105 crankset a couple weeks ago, and the thing is so flexy compared to Dura Ace or my old FSA crankset that it's not really worth the cash, IMO, to put nice crankarms on flexy rings.

As you have noticed, it may be hard to find 165mm cranksets anyway, stock. So ordering the cranks separately and sticking with the same level of componentry is probably the way to go unless you want to go all out with the upgrades. In that case, you can see if your shop can custom order you a new triple (in Ultegra or DuraAce 7800 (old DA), say) with 165mm arms or swap out whatever stock arms they can find with 165mm ones for free.