My brother and I are considering going on a tour of Europe, that visits 13 countries in 24 days. Most advice I've seen recommends buying a separate SIM card for each country, but that is expensive when you are visiting many countries. We want access to cheap calls/texts that are local for the country we are in as we would mainly be calling each other or using Rebtel if we wished to make an international call/text. Do there exist European cap plans that allow you to use your phone in multiple countries without having to pay roaming charges?
Although this has been phrased as somewhat of a shopping-related question I'm going to answer the issue of short trips in multiple countries and having an easy way to stay connected to each other. I'm not going to cover calling abroad/home as you've already got that sorted, so I'll concentrate on calling locally (between the two of you and other locals)
Europe now have a regulation to try and stop the 'bill shock' when roaming, so in general you should get 'reasonable' roaming prices from your own operator, although the usual rule of shopping around is advised.
Roaming SIMs. If you want to get a single SIM card you're going to come across companies such as Maxroam and Truphone, which offer a single SIM which is pretty much always roaming, but they make special deals to try and lower the average rate. These would in no way replace a regular SIM for a local person, but for someone on a fleeting visit it's an option, but in terms of cost, compare with your own operator for the countries you'll be visiting, as they could still be expensive. Remember also that these SIMs won't give you local numbers in each country, so getting calls in won't necessarily be local calls.
Calling cards (of which there are hundreds of brands), and services such as Rebtel are useful but are dependant on either using landlines/payphones or tethering to WiFi.
Local cards. This is only going to be relevant if you're in a single country for a reasonable stay (eg. a week), otherwise you're going to end up with many cards with half-used credit on them. I would definitely recommend these if you are staying long enough to warrant it, as the calling costs are going to be the cheapest, and importantly (for me at least) data is going to be a lot cheaper than when roaming.
If you're looking for data while roaming you might want to check out this wiki in order to get a good view on what is available (it's reasonably current with the services, but don't trust the prices too much).
SMS is your friend. If you're going to be trying to coordinate with each other using your phones, try to use SMS, since there's a limit in Europe of 0.11EUR per message sent, and of course free to receive, so it's going to be cheaper than both of you paying roaming fees. Of course you'd probably want to discuss what messages to send though, since you'll avoid back-and-forth messaging if you make sure to cover all the info in a single message. Also, missed calls are your friend... You can easily have a confirmation signal if you agree that you won't call each other, and then a missed call will mean something.