Yep, I'd return it immediately, the sooner the better. And I'd ask for refund in kind (cash, credit card, whatever), not just store credit. Any reputable hat vendor knows that hats rarely 'loosen up' with wear. Best case, you had an ignorant salesperson - worst case, you were knowingly sold a pig in a poke to clear out inventory. Either way, I think they should make it right and try to get you in a hat you want, and that fits properly.
PS - I've never had a stretched hat stay stretched. I once bought a straw hat in the same way and it had shrunk back by the end of the day. Luckily it was a $30 hat, and it wound up fitting a friend so it didn't go to waste. I wouldn't be so amused if the same thing happened with a Borsa, however.