Does Medicare send your billing service payments made out to you directly? If not, I don't believe you have to change your address with them. If they do, it would be either form 855-R for reassignment of benefits to your company, or 855-B for other organizations.