Using a decorator seems to be overengineered because we can use a simpler code also without modifying the class internals:
service = NotificationService()
service.sender = SmsSender()
Moreover, in your test test_notify_with_sms, what's the point of a decorator if the sender method still needs to be overwritten? We should overwrite service.sender because sms_stub and service.sender are different instances of SmsSenderStub.
In this context, your example seems to be an anti-example.