Use - to indicate NOT.
For example, to query documents with id not starting with A59, the query would be: -id:A59*, that is: /solr/select/?q=-id:A59*
To delete by query, post the query in a delete message to the update handler, as specified here.
EDIT: NOT (all uppercase) can also be used as boolean operator