Notorious enemies will show a White Star above their avatar.
Notorious Enemies are the strongest type of enemy, and will only spawn for those capable of dealing with them. This means you must have high leveled weapons and armor to be able to spawn Notorious enemies.
HOWEVER, having lower level weapons does not make you immune to Notorious Enemies. If someone else spawns them and leaves, you may still be able to find a Notorious or two lurking in the shadows. Notorious Enemies DO give more Cash and Experience, but be cautious - a Notorious could easily dispatch you if you aren't prepared. Keep Painkillers on hand.
Notorious enemies also offer the highest chance of Class Tokens dropping.