Short Answer: Don't try to delete Spam. Instead move it to the Spam folder (where it is periodically deleted).
The important thing to remember about GMail is that it uses a tag or label-based system for organizing mail, rather then the traditional folder organization. For example, rather then keep new messages in an Inbox folder, GMail just labels new messages with the "Inbox" label. To remove a message from the Inbox, you "Archives" the message, which removes the label. Messages can have any number of labels. Typically you never deletes messages in GMail, you just remove labels. A message with no labels can still always be found in the "All Mail" psuedo-label, which is really the list of all messages not labeled Spam.
GMail's IMAP interface maps this label system to folders, but it can never be a perfect match. Mail.app uses GMail's IMAP interface, so some operations can be mysterious. In particular, the IMAP Delete command is mapped to GMail's Archive command, so deleting in Mail.app is really just removing a label.
This makes the "All Mail" folder particularly strange. Since "All Mail" is not a real label in GMail, messages cannot be deleted from it via IMAP because Archiving a message in "All Mail" is basically a no-op (there is no label to remove). So, as you have observed, there is no way to delete a message in the "All Mail" folder (in the standard IMAP setup -- you can truly delete message via the GMail web interface).
The Spam label in GMail is special, because anything labelled Spam will not appear in the "All Mail" psuedo-label. So in Mail.app, rather then trying to delete spam messages from "All Mail", you should label it Spam by moving it to the Spam folder. This has two benefits, first it will remove the message from "All Mail" , and second, it will teach GMail that the message is spam. This will cause GMail to adjust its Spam filters to automatically classify Viagra emails as spam. If you don't mark Viagra emails as spam, GMail may conclude you actually want those emails.
Recently, I've noticed a change in GMail/Mail.app interaction. When I move a spam message from Inbox to the Spam folder, the message won't immediately disappear from the Inbox. Instead it will become gray. I think gray messages are cleaned up and removed periodically, but you can force the cleanup by selecting Mailbox>Erase-Deleted-Messages.
Hope this Helps - Chuck