Query notifications and connection options
The explanation to this problem turned out to be an issue with another part of the application explicitly opening read uncommitted connections. These read uncommitted connections were then left in the connection pool and reused by service broker, which can't operate using this isolation level.

The solution was simple: Make sure service broker is connecting with a different connection string, thereby using a different connection pool.