Figured it out, I think. As I said, I've done the "Delete all notifications" thing several times, and there was nothing available under "all notifications" once I did. It seems that this doesn't actually remove the notifications, only the ability to access them from the main "Notifications" app screen. When I got a notification, I went in to the list (not just the notification its self) and started scrolling. Once I got all the way to the bottom, there was something there from a number I didn't readily recognize and was listed as a "hidden message." Once I cleared it, my notifications seem to be correct. No clue what that was or where it came from, as I didn't have any corresponding messages on my phone.