I'm curious, is it uncommon to have packages delivered to the mailroom at your place of work? That's what I've done for the last 4 years and I've never had a problem.
It is not uncommon, but at a mid-sized company it is a bit problematic: when the receptionist has to handle private parcels for a couple of individuals, that is OK; but when there are 100-200 employees and they regularly order non-work related stuff at their company address, it becomes a burden on the receptionist, burden that is not part of what the company pays him for.
So :
* small company where everyone takes care of (his own) deliveries: OK.
* smallish company company where there is a receptionist: OK because it does not happen too often.
* middle-sized company: not OK.
* large company with a dedicated mail/parcel/delivery service: I guess it depends on formal work agreements.
-We solved this in a simple manner at a former employer - we just had everybody who wanted something sent to work have it addressed to such-and-such, room 40.
Room 40 was a bench behind the warehouse reception.
Of course, there are potential pitfalls here - say, assuming your colleagues to be honest, for instance - but to the best of my knowledge, we never lost a parcel in years. (Which is more than could be said for anything entering the murky depths of our ERP system...)
At AOL in late 2001 they insisted that employees cease receiving non-work packages at work. The legit concern was the anthrax being mailed to DC area offices. That was also just past "peak AOL" so I was soon freed from this problem, with a decent sverance to boot.
I have found ordering from B&M's via their websites and picking the thing up at the store bypasses this whole problem.
I experienced the receptionist losing track of my stuff once and it was a really uncomfortable situation because, obviously, you're still colleagues and you don't want to get too pushy, but at the same time, where the hell is the stuff I paid for? After that I stopped having stuff delivered to my office.
And anyway you may not want everyone to know what you are buying.