I have never had an issue getting an unlock code for free from At&t, but then I have been a good customer, pay my bill for about 8 years now.
I do recall there was some law passed recently (last few years) that requires them to give it up, not sure if there is a time period. My last one I just sent an email and requested it. I got a reply with complete instructions and the codes for my Blackberry and Motorola Razr.
In the old days before that law, I would just call their international division and tell them a little white lie. I would say I was going to travel outside the US and wanted to unlock my device so I could use pre-paid SIM internationally.