How does ARP take care of uniqueness of physical addresses?
How does an ISP allocate a MAC address when I do not have an NIC( Network interface Card)?
ARP does not take care of address uniqueness. That's not arp's job. It assumes the addresses are unique and will fail if they are not.
Your second question does not compute for me. I would assume that you are running slip or ppp or something like that. If you really have a mutant ISP that is assigning you a MAC address, you need to determine which type of mac address it is. If it's a ethernet address, your ISP could apply for a block of ethernet addresses. The ethernet address has two parts: a manufacturer id and unique address within the manufacturer id. Other lans work the same way.
To support their switchover product, HP would give out ethernet addresses not assigned to any hardware. All of HP's addresses are unique to HP. And it's up to HP to make sure that they don't give out the same address twice.