That native English language user sounds like he was being extra harsh that day. Unless he was your writing instructor, and he was correcting your essay or exam, I don't think it was necessary to correct that sentence.
However, if you really think about the grammar involved, he does have a point. The second sentence is the one that is a bit off (a very tiny bit, though).
"Whoever" is a noun, and "whoever picks up the phone" is a noun phrase. So just sticking a noun phrase in the middle of a sentence with no predicate attached to it isn't quite right, even though it sounds OK to me, and as a native speaker I might easily say it without being corrected by others.
On the other hand, in the first sentence, the "no matter who ..." construction is idiomatically an adverbial phrase, and when you stick it into that same sentence (in the same place), it functions as a modifier of the whole clause, "your record can be pulled up faster." This usage sounds fine too, and I think it is more in keeping with formal grammar rules.