Attestation application doesn't mean you don't have bad programs installed, it tells you only that the system hasn't been modified.
I've never heard of number spoofers using SMS, since replying to them obviously would just reply to YOU. Usually number spoofing is used for voice calls. These messages... what kind of data do they contain? URL's?
Since you say you only have the stock GOS applications installed on your phone, a factory reset shouldn't be too burdensome. That's the first thing I'd try to make sure that there isn't any malicious software stuck in there somewhere. So give that a go as a first step, if the malicious SMS messages don't stop, take it up with your service provider and see what they say about the messages. They should be able to pull up a log of messages sent from your phone, which will help you narrow down if your phone actually sent the messages.