重要なことを見逃したようです：
今までは独自のスレッドを開始するアクティビティがありました。このスレッドは、同じアクティビティにある Handler の sendMessage() メソッドを使用して、時々メッセージを送信します。それはうまくいきます。
ここで、バックグラウンドでいくつかのクールなことを実行するサービスを追加しました。この Service 自体は、Activity にある Handler の sendMessage() を呼び出すという同じ方法を使用して、いくつかのメッセージを送信しようとします。しかし、これらのメッセージは散発的にしか到着せず、その多くは失われます。
サービスが関与している場合、メッセージ/ハンドラーに何か違うものがあるようですか?
ありがとう！