I'm looking for some kind of voip or telephony service that will:

a) give me a US phone number.
b) play a single recording at that number
c) immediately submit the phone number of each incoming caller to some
simple web API.

The only requirement is that the line should be able to handle some
number of multiple calls at once.  And it would be able to scale up to
increased volume over time.

An acceptable answer would be the names of a few companies that
provide this service, or a simple "roll yer own" approach using some
more general voip service.

What you need is an Interactive Voice Response Service (IVRS) hooked
to a SIP/VOIP account with PSTN termination.

You can google around for free IVRS software or you may opt to use
open source solution like Asterisk. Asterisk can playback music or
voice recordings using music on hold feature (see:
http://www.voip-info.org/wiki-Asterisk+config+musiconhold.conf) or you
can even use a computer generated voice to read out a text. Then you
can make Asterisk load an external URL with the caller's mobile number
as a parameter (see:
http://www.voip-info.org/wiki/index.php?page=Asterisk+cmd+Curl). The
web application related to the URL can then do anything to the data
like simply logging it, forward the time and mobile number to email or
even forward it as a text message.

Finally all you need is to connect you SIP address to a real phone
number so that regular phones can call your IVRS (see:
http://www.voiptalk.org/products/0871+UK+PSTN-2-IP+National+Number)

For the short list of companies that offer this service, you may try
http://www.evoice.com/ which forwards voice mails to email, then all
you need is a web script that reads your email and look for the
forwarded voice mail, then call the external URL. You may also email
info[-at-]fingerapps[-dot-]com if you want a company to build the
entire system to your specification.