Where do these strange contacts come from?
This is often caused by linking other social networks (via the appropriate App) or third party E-Mail providers to the Android device. This will cause the contact lists or address books to be synced and shown in your device.

This includes for example


Last FM
Yahoo Mail
Skype
etc.