Perhaps the op just doesn't understand the process and what it does. So, maybe a more detailed explanation is in order.
When you get an Android phone from a carrier store it is loaded with firmware (Android + their own stuff) provided by the carrier. The phone is set with administrative access locked so the user cannot change this. They will include a number of apps that are unique to the carrier and while many consider them unnecessary and intrusive, they are not "malware". You will hear them referred to as "bloatware" most of the time. These apps are in the protected system area and cannot be removed unless root (administrative access) is achieved.
When a phone is turned on for the first time, it will search for networks and connect to the appropriate one provided the device identified itself appropriately (SIM for GSM networks, ESN for CDMA ... ie. Verizon networks.) A Verizon phone must be activated on their network and the activation follows the device. With a GSM network (Like AT&T) the activation follows the sim card, so you can have 5 phones and all you need to do is put the sim in it. With Verizon, you have to deactivate the current phone to activate a different one. Essentially, either way, it's one phone at a time for that particular number.
Once it boots for the first time, it creates a user account. Some devices allow multiple users, but that a different kettle of sheep. Information for this account is stored as user data, like messages & email, logins, free apps, paid app keys etc. Then there is a user storage area where you keep your pictures, music, videos and any other files you might have. These are kept in a folder called /sdcard.
When you perform a factory reset, the phone erases the user data portion of the phone and flushes the system cache. This effectively erases any personal credentials, messages, apps and settings. It shouldn't touch the user storage folder, but sometimes it does making backups and cloud storage very important for files you don't want to lose.
What this means is that any app, setting or login installed since the phone was turned on the first time (ie. from the "factory") is wiped when you reset it. What stays behind are the carrier apps installed at the factory, any user files in /sdcard and, because some apps store data in the /sdcard folder, you may have remnants of them as well. To ensure a perfectly clean reset, you should also format the /sdcard to wipe that clean too.
From a security standpoint, an unrooted Android phone is very safe as long as you are careful about the apps you install and that you only get them from legitimate sources. Downloading apps from "alternate" app stores in an invitation for malware.
As for the phone call ... as everyone else has said, it was a test call. Resetting your phone will remove the number from your phone, but since the call was placed successfully, you can still see it in your Verizon account. Other than compromising the privacy of the person the rep called, there's no harm in it, although it's probably not a good practice to call private numbers to test. Maybe the store number was busy? Who knows.
