It has been a while since I had to dig into notifications, but here's what I remember:
The sweep proc that tries to send notifications attempts to send all the ones for which notification_user_map.sent_date is null. So to remove the offending messages from the queue, you can either fill in the sent_date, or delete all the ones whose sent date is null.
It gets more complicated if you also have good notifications in the queue, but it sounds like you haven't had it working yet so that isn't a problem.
Now, if this does not make the problem go away... I'm looking at the notifications code and it appears to get the "notification-test1" piece from the package parameter called EmailReplyAddressPrefix. That's where I'd look first for a trailing space.
Hope this helps...
