I've played in and run evil campaigns of various sorts in both 3.5 and 4e (though not 5e, I think my learning will transfer), and run into a lot of problems: My Guy Syndrome comes up a lot, as does a tendency to default to a regular D&D storyline only with more stealing of spoons and kicking of puppies to remind ourselves we're evil. Sometimes an evil campaign instead descends into over-the-top motiveless violence until there's no story at all. There's a whole host of at-the-table and in-the-story issues, and I tried many different strategies to address them. Eventually I came up with a framing device which works well for us in avoiding these problems:
Provide the PCs with a Master to guide them toward orchestrated works of Evil.
Start the game with the PCs as underlings/minions/hirelings/apprentices/etc of a powerful evil NPC. The Master has a complicated Evil Plan and he tasks his minions to enact various parts as the Plan progresses: "Bring me the soul of a hound archon," "Raze the border keep," "Steal the Apocalypse Gem," "Help a spy infiltrate the paladin's ranks," and so forth, tailored to the PCs' abilities.
This provides the party a reason to work together despite having different agendas (and working together will hopefully bond them as friends so that they want to continue as a group) and establishes small achievable evil goals that accumulate into an Epic Evil Event.
All you need to do is ask the players to make sure their characters have a good reason to work for the Master: The serial killer likes having his rampages subsidised (and the Master protects him from the Law); the necromancer seeks to learn from the Master's experience and gain access to his libraries of forbidden lore; the mercenary's in it for the money and benefits.
Eventually the Apprentices will surpass their Master.
Expect the party to betray their Master at some point, hijacking his Evil Plot for their own gain: this is not only expected, but awesome. It's the Master's Evil Plot, not yours, and the story isn't about the Master--it's about his apprentices. Consider the Master to be training wheels for evil, setting an example which the party can then follow to surpass and overthrow their instructor as they level up.
This works because Evil Needs Goals.
As Ed describes so well and AgentPaper elaborates in the D&D context, evil needs concrete reasons motivating its actions. The Master provides goals and motives while the players find their feet in the new paradigm, channeling and guiding their exploration of what it means to be evil in ways compatible with the D&D paradigm without simply kicking puppies during a dungeoncrawl.
A word of warning: Alignment is tricky.
D&D has a history of the details and nature of alignment sparking major heartfelt arguments, because D&D alignments are not easily (or appropriately) matched to real-world philosophies and moralities; they're narrative simplifications to support the game's conceits and draw their power from storytelling conventions rather than from genuine moral complexity. Exactly what this means and how to deal with it are beyond the scope of this answer (and possibly this site, although there's a LOT of questions on the topic you can look at), but you should be aware it exists and be ready to talk with your players about what "Evil campaign" means to them so there aren't nasty surprises mid-game.
Spectators are not bodyguards.
In 5e, the rules do what they say they do (and anything else is up to the DM to decide). The target of a Spectator's attention is "a location or treasure". Its remit is "allowing no creature but its summoner to enter the area or access the item..."
A living creature is not a location, not a treasure, not an area, and not an item.
Even if it were, though, it wouldn't have the effect you want. It doesn't bodyguard, it prevents access. Even if it could be assigned to a person it wouldn't be able to distinguish between stabbing them with a knife and shaking their hand. A bodyguard that can't tell the difference between those two things is not a particularly effective bodyguard.
As far as the necklace, that could work. It's a legitimate treasure, no one's stolen it, and nothing says that a Spectator has to stay in one place.
It would certainly help to prevent anyone from stealing the necklace from you, or from taking it off your cooling corpse. On the other hand, it's going to do very little to the part where they convert you into a cooling corpse in the first place. What does it matter to the spectator if someone shoots you full of holes? You're not the one it's guarding.
...and if somehow you convince the spectator that everyone who gets within 20 feet of the necklace is a threat? Well, have fun walking down a city street.
This is not what this tool is for, it is not suited to the purpose, and it won't work.
There are other ways, though.
A spectator is, among other things, a LN creature with int 13, who's capable of communicating via telepathy. If you really want a spectator to help you out, you can talk with the thing, and possibly convince it. The ritual even gives you a way of making one show up and be non-hostile. So, for example, if you're absolutely confident of your ability to bluff the spectator into doing whatever it is that you want it to do in the moment, then binding one to a necklace that you can wear is a pretty reliable way of always having a spectator on hand to bluff.
Alternately, the spell only binds them for 101 years. After they're free of it, they pretty much become free-willed. At the same time, many of them continue to do whatever it was that they were doing before (more or less) out of habit or lingering fondness or some such. If you are particularly long-lived, you might be able to befriend one in the century+ of its servitude, and still have it as a friend when it was done.
None of this will give you guaranteed loyalty or obedience, and it all requires more effort than just "Perform ritual. Receive bodyguard." Also, the Spectator is both an aberration and insane, which is likely to complicate the process. Still, if what you want is a friendly eyeball-critter, it's at least technically possible to befriend an eyeball-critter.
Of course, if you're the DM...
Well, a spectator is summoned and bound through a specific ritual that does a specific thing. It would be entirely reasonable to suppose the existence of a similar-but-distinct ritual that did a similar-but-different thing of summoning a spectator (or something very much like a spectator) as a bodyguard. If that's something that you want to have in your game, it's an entirely reasonable thing to have in your game.
Best Answer
All the information about flameskulls in 5e is on page 134 of the Monster Manual.
It is stated that a flameskull "only dimly recalls its former life," but this refers to the life it had before it became a flameskull at all. There is nothing to suggest that flameskulls have a poor memory in general.
In the description of the flameskull's rejuvenation, it says, "If it can no longer fulfill its intended purpose, the re-formed flameskull is beholden to no one and becomes autonomous." This suggests that the flameskull can remember things (such as its orders) from before its rejuvenation.
A flameskull has an intelligence of 16, suggesting it should be able to plan and reason strategically. Casting fireball the moment it rejuvenates seems like a reasonable strategy if the last thing it can remember is being smashed the moment it rejuvenated.