I'm quite used to using the phrase "at your earliest convenience" to express urgency but also polite sensitivity to others' schedules and deadlines. It means "Please do this as son as you can without dropping something else."
Lately I've heard more and more voice mail greetings and written notes that use the phrase "at my earliest convenience." To me, this is rather rude, since it means "I'll do it when I feel like it." More to the point, politeness requires minimizing the bother of a request on oneself while expressing appreciation for the bother of a request made on someone else.
Am I reading too much into this? Is it polite to use "at my earliest convenience?" It certainly sounds rude to me.