Jag hittade en anledning till varför detta skulle hända. Användaren hade lämpliga behörigheter, men den lagrade proceduren inkluderade en TRUNCATE uttalande:
TRUNCATE TableName
Sedan TRUNCATE tar bort objekt utan att logga, behöver du (tydligen) förhöjda behörigheter för att utföra en lagrad procedur som innehåller den. Vi ändrade uttalandet till:
DELETE FROM TableName
...och felet försvann!