I would like my order numbers to be a little more controllable than just starting at 00001 for the first order. Ideally, I'd like to specify an alphanumeric prefix. Any suggestions?
My immediate problem is I'm working on site No 2 and my PayPal sandbox account won't process payments because the Invoice Id has already been processed. (due to testing on site 1)

I've noticed there's a Reference field on the Order db Object which you should be able to set somewhere and then use it in the Paypal payment.
I'm not sure where to set it though, I'm relearning everything after a long Hiatus

Coming back after a long hiatus – sounds familiar. Its that reference field I want. I'll see how I can set it. Ideally I'd reset it at the start of each year to something like 20160001.

This answer comes maybe a little late.

There is a hook in the Order model to override the reference number. Like this:

/** 
 * shop.yml
 * Order:
 *   extensions:
 *     - Order_Extension
 */
class Order_Extension extends DataExtension
{
	public function generateReference(&$reference)
	{
		$reference = date("ym") . str_pad($this->owner->ID, 6, '0', STR_PAD_LEFT);
		$candidate = $reference;
		//prevent generating references that are the same
		$count = 0;

		while (DataObject::get_one('Order', "\"Reference\" = '$candidate'")) {
			$count++;
			$candidate = $reference . "" . $count;
		}

		$this->owner->Reference = $candidate;
	}
}

I don't know about my refference number genereration is the best. If you want a totally uniqe reference, this pattern look good:
http://stackoverflow.com/a/22279165/2955413