volts drop = current * resistance. a starter can draw around 200 amps, so you will see from the equation that that even a .01 ohm resistance in the starter circuit can cause a full 2 volt drop, making the starter turn slow.
you are on the right track checking for voltage. now here is the extra info you need:
Any part, connection, or wire that is introducing resistance will cause a voltage drop. While cranking the engine (explaned later), measure voltage across each part of the system, starting with the battery terminal and the connector at the battery (this will tell you if the connection needs cleaning), then across the cable between the battery and the starter relay (this will tell you if the wire is good), then the cable and the terminal at the relay, then across the relay, then the next relay terminal and the cable connector, then across the cable between the starter relay and the starter, then across the connector and the starter terminal, then the engine to the cable at the engine, then across the negative cable, then across the negative cable connector and the negative terminal at the battery.
This will test every connection, every wire, every solenoid, ect....
in order to measure an accurate voltage drop, the full starter current must be flowing, therefore you will have to crank the engine for each test. Example: if you hooked a little light bulb up to make current flow instead of the starter, the voltage drop will be MUCH lower across each test because there will be much less amperage draw.
most don't realize how little extra resistance it takes to mess with a starter (because it draws a lot of current, and in this case there is only 12 V to begin with). if each of those connections are causing a voltage drop it adds up.
Specs to look for:
If you get a 0.0 V drop, then put your meter in mV to make sure.
0.0 V drop across any connection -clean the connection if higher
0.0 - 0.2 V drop across wire - replace the wire if higher
0.0 - 0.3 V drop across the solenoid - replace the relay if higher (this one i am guessing a little, but if it is much higher it should be replaced.)
Keep in mind that if the voltage to ACTIVATE the starter relay is dropping off, or the starter relay has a bad ground, that it may not be able to fully switch on, which will also cause a large voltage drop across the starter relay mentioned in the test above.
The starter will cause a voltage drop, this is not measuring the voltage drop across the starter when done correctly. it is measuring the voltage drop across every possible other thing that (and mostly likely-since you have a new battery that is fully charged) is causing your problem.
Do this when everything is hot, relays ect may work great when cool, but malfunction when hot. If everything is in spec, and your battery is fully charged, your starter itself may be causing to great of a voltage drop when it gets hot. since it is new, a heat shield or similar may be needed.
Hope this helps :beer
on a side note: if you know for a fact that the wire, relay, ect is good (brand new) and you still have a voltage drop greater than listed above, then that means you need beefier wire, connector, relay, ect. for the current you are trying to draw. Also trying to read resistance instead of a voltage drop in this situation will not give any indication (unless it is flat out an open circuit-but yours isn't), as it would take a much more accurate meter than any typical mechanic owns due to the high current draw. However the voltage drop is measurable.