I would like to start a website with the .me TLD and this domain name should be the brand name as well.
But as all .yu domains have been deleted, I'm a bit cautious.
Is it safe to register a .me domain? Is it possible that this domain name will be removed as well after some years?
Actually, .ME domains are perfectly safe - it is the ccTLD for Montenegro delegated by IANA and operated by a joint venture of Afilias, Godaddy and Me-Net (see http://www.domain.me/who-is-me ). Also they are being used by the biggest Internet brands like Facebook (fb.me), Yahoo (me.me), New York Times (news.me), Wordpress (wp.me) etc.
As for .YU, it has been shut down - but domains have not been deleted... They have been migrated either to .me or .rs. I would strongly recommend registering .me.
With all the nonsense domain names out there that have had great success, e.g. woofu.com, joomla.com, and, dare I say it, yahoo.com, don't get too caught up in the name itself. A lot has been written about this elsewhere but the bottom line is this: a good name won't save a bad product and silly name won't hurt you. These .me extensions are about vanity. It is not where the rubber meets the road.
Our company faced a similar decision when we rebranded our production company. Trying to find available domains to support the rest of the branding was challenging.
In the end we made the decision to move forward with a .be domain. We did purchase a "not-very-good" .com as backup in case at some time in the future we couldn't use .be any more.
(Not to be self promotional -- but the company is Busy Worker Bee (busyworker.be) and we use the bee, hive, honey, blah blah metaphor in our sales and marketing)
We have found that our clients enjoy it, and it always makes for a nice elevator smile.
Based on this experience I say -- go for it!
It is ok with Country Codes when you business is in some particular Country (and you clients too). In other cases, I will avoid CC domains at all. Most of the noise around .me, .ly and other strange extensions is just marketing from GoDaddy and other registrars. They make millions of each new extension. You can consider additionally that most of CC are under non US jurisdiction.