I tried minimizing the impact of checking for a free spot in some ways.
Every apple or spike is added to a group and on every spawn attempt I go through this list checking the distance squared (to avoid a square root calculation) to the position I want to spawn. If it's bellow a threshold I'll elect a new point and start again.
On each frame that I want to spawn I limit the number of searches. If I reach a limit on that frame I won't spawn a new object, to avoid hanging up the game.
Even then I would probably remove this random factor in future updates and go with your idea of various levels with different map layouts. It would probably have objectives as well.
Good idea about the rotten apples, although I would probably not remove a segment because that's actually a bonus. One effect could be that the snake gets sick, which makes her minimum head size a little larger for some time.
Thanks for your reply and suggestions.