I managed to put something together by:

Changing the basket/checkout processes to allow negative quantity values
Changing the checkout process to not automatically change to "gift voucher" payment type on negative values
Changing the shopping cart class to disallow negative values from being entered
Changing the checkout process to show tax on negative values
Changing the currencies class to show negative amounts nicely
Adding new payment and shipping types called "credit note"

Negative quantities can now be added to a customers cart, and be checked out, resulting in credit note.

However...

I need to add an Admin interface function to place negative quantities in the cart (I currently use an Access database for a lot of Admin stuff, but most people won't want to do this, or won't have remote direct database access - other than phpmyadmin - unless they use a php bridge or something). But I think this should be fairly straightforward.

I need to edit the orders.php to send a different email (or easy - no email) if it's a negative total.

This works for me, although my php skills are basic at best. But on this basis - unless I've overlooked something drastic - it would be fairly easy for a more competent php coder to come up with a mod.

Sorry if this hasn't helped...